CF1023B Pair of Toys 题解

简化题意

求 1 到 n 中取两个数，问有几种方案。

做法

Unaccepted

直接暴力，枚举两个数（因为题目中说了选 a b 和选 b a 都是相同的，所以可以直接枚举所有 a < b 的 a b）。

#include<bits/stdc++.h>
using namespace std;
long long n,k;
long long cnt;
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n>>k;
	for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) if(i+j==k) ++cnt;
	cout<<cnt<<endl;
	return 0;
}
//TLE on #4

正解

刚刚上面的做法太暴力了，因为它 Θ(n²) 的时间复杂度以及 1 ≤ n, k ≤ 10¹⁴ 的数据范围 TLE 掉了。

现在我们先进行一些数学的证明：

∵a + b = a + b

∴ a + b + c − c = a + b

∴ a + c + b − c = a + b

∴ (a + c) + (b − c) = a + b

所以我们知道当 a + b = k 时 (a + 1) + (b − 1) = k。

而且第一组物品就是 0 k - 1。

但是如果 k 大于 n × 2 − 1 就无解了。

因为最大的一组是 n n-1，所以最大的一组和就是 n + n − 1 ,k 大于它就无解了。

于是判断一下 k 的奇偶性再在第一个数和第二个数的个数之间取 min  就行了。

上代码：

#include<bits/stdc++.h>
using namespace std;
long long n,k;
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n>>k;
	if(n*2-1<k) cout<<0;
	else if(!(k&1)) cout<<min(k/2-1,n-k/2);
	else cout<<min(k/2,n-k/2);
	return 0;
}