题目大意:T组测试样例,接下来两个整数,表示正方和反方的人数,有三局比赛,问如何安排各自的人数使得正方必赢,并且正方存在一种安排策略使得反方无论如何都无法赢就输出Yes,否则输出No。同一个人只能参加一局,一局中如果正方人数不小于反方则算正方该局赢,参与三局两胜制。
思路:每局可以不派人,如果正方存在的最优策略一定是平均把人数分配到三局游戏中,而反方想赢就必须把人数集中到其中两局,并且这两局都要赢,那么反方赢面最大的选择就是赢得正方人数最小和第二小的那两局,说明反方的人数如果比正方这两局人数总和多2人(一局多一人)或者更多No,否则Yes。
- 这种策略最直接的就是线性规划:设正方三局游戏分别为x、y、z人,则Yes的条件就是: x+y>=m−1,x+z>=m−1,y+z>=m−1,x+y+z=n,相当于正方任意两局的人数都不会让反方多2,把四个式子合并一下刚好能凑出: 2n>=3(m−1)。
Code:
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cmath>
using namespace std;
int main() {
int n,m,T;
cin >> T;
while (T--) {
cin >> m >> n;
int a = m / 3;
int b = m / 3;
if (m % 3 == 2) {
b++;
}
if (n > a + b + 1) {
cout << "No" << endl;
} else {
cout << "Yes" << endl;
}
}
return 0;
}