题目大意: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 x + y >= m - 1 , x + z >= m - 1 , y + z >= m - 1, x + y + z = n x+y>=m1,x+z>=m1,y+z>=m1,x+y+z=n,相当于正方任意两局的人数都不会让反方多2,把四个式子合并一下刚好能凑出: 2 n > = 3 ( m 1 ) 2n >= 3(m - 1) 2n>=3(m1)

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;
}