洛谷 AT_arc171_a [ARC171A] No Attacking 题解

分析

显然，在一个 $N\times N$ 的网格里，如果要放超过 $N$ 个车，那么是肯定无法完成的。

很明显，车放都在偶数行是最优的，如果不够了就放在奇数行，然后再把所有的兵都放在奇数行。

还可以知道，对于一个 $N\times N$ 的方格，一共会有 $\lfloor \frac{N}{2}\rfloor$ 个偶数行，$\lceil \frac{N}{2}\rceil$ 个奇数行。

若：

• $A\le \lfloor \frac{N}{2}\rfloor$：这时刚好所有的奇数行都不会被车吃到，但有 $A$ 列会被车吃到，所以这时有 $\lceil \frac{N}{2}\rceil \times (N-A)$ 个位置可以放兵。
• $A>\lfloor \frac{N}{2}\rfloor$：由于偶数行只能放 $\lfloor \frac{N}{2}\rfloor$ 个车，所以这时会有 $A-\lfloor \frac{N}{2}\rfloor$ 个奇数行能被车吃到，故只有 $\lceil \frac{N}{2}\rceil -A+\lfloor \frac{N}{2}\rfloor$ 行能够放兵，而由于有 $A$ 列会被车吃到，所以只有 $(\lceil \frac{N}{2}\rceil -A+\lfloor \frac{N}{2}\rfloor )\times (N-A)$ 个位置可以放兵。

然后再判断能不能放下 $B$ 个车即可。

Code

#include<iostream>
#define ceil(n) (n%2?n/2+1:n/2)
using namespace std;
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t,n,a,b,sum;
	cin>>t;
	while(t--) {
		cin>>n>>a>>b;
		if(a>n) {
			cout<<"No\n";
			continue;
		}
		sum=(a<=n/2?ceil(n)*(n-a):(ceil(n)-a+n/2)*(n-a));//计算能放的兵的数量最多是多少
		if(b<=sum) cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}