CF1023B Pair of Toys 题解

简化题意

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

做法

$\color{red}{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

正解

刚刚上面的做法太暴力了，因为它 $\Theta(n^2)$ 的时间复杂度以及 $1 \le n,k \le 10^{14}$ 的数据范围 TLE 掉了。

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

$$\because a + b = a + b$$

$$\therefore a + b + c - c = a + b$$

$$\therefore a + c + b - c = a + b$$

$$\therefore ( a + c ) + ( b - c ) = a + b$$

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

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

但是如果 $k$ 大于 $n \times 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;
}