Ball in Berland - 洛谷
题意
在毕业典礼上，有个男孩和个女孩准备跳舞，不是所有的男孩和女孩都准备结伴跳舞。
现在你知道个可能的舞伴，你需要选择其中的两对，以便使没有人重复地出现在舞伴里，求可能的数量。
思路
暴力
最朴素，也是简单的方法，就是通过暴力组合进行配对。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6;
int a,b,k,boy[maxn],girl[maxn],ans;
int run()
{
ans=0;
cin>>a>>b>>k;
for(int i=0;i<k;i++) cin>>boy[i];
for(int i=0;i<k;i++) cin>>girl[i];
for(int i=0;i<k;i++)
{
int t1=boy[i],t2=girl[i],flag=1,cnt=0;
for(int j=i+1;j<k;j++)
{
if(t1==boy[j] || t2==girl[j]) flag=0;
else
{
ans++;
}
}
}
cout<<ans;
}
int main()
{
int t;
cin>>t;
while(t--)
{
run();
cout<<endl;
}
}
然而，会在第四个点超时，所以还得优化
利用桶进行优化
我们注意到，超时的原因就是这段代码：
for(int j=i+1;j<k;j++)
{
if(t1==boy[j] || t2==girl[j]) flag=0;
else
{
ans++;
}
}
那么，该怎么进行优化，使其从变为呢？
这段代码的用途其实就是在，后面查找有没有重复出现的人。关注题目中的数据范围：，，因此可以开一个桶来存储男生和女生各出现的次数，然后再与当前，作差即可
手玩一下样例：
最开始的桶是这样的：
| BOY | 2 | 1 | 1 | |
|---|---|---|---|---|
| girl | 0 | 2 | 1 | 1 |
随后，对进行判断，ans=剩余组数()-重复数量()，即
然后，桶变成了这样：
| BOY | 1 | 1 | 1 | |
|---|---|---|---|---|
| girl | 0 | 1 | 1 | 1 |
为了避免重复，每次计算完1组后都需要更新一下对应的男女生人数。进行完的操作后，
随后是这样：
| BOY | 0 | 1 | 1 | |
|---|---|---|---|---|
| girl | 0 | 1 | 0 | 1 |
继续进行如上操作，，更新桶
接着：
| BOY | 0 | 0 | 1 | |
|---|---|---|---|---|
| girl | 0 | 0 | 0 | 1 |
当只剩1组时，意味着枚举结束了，并输出为
整个程序的时间复杂度是，CF的机子慢所以算精确点，不会超时
另：十年CF一场空，不开见祖宗
代码
#include<bits/stdc++.h>标签：boy,Ball,int,题解,t2,t1,CF1475C,ans,girl From： https://www.cnblogs.com/lyk2010/p/17850331.html
#define int long long
using namespace std;
const int MAXN=2e5+10;
int boy[MAXN],girl[MAXN],a,b,k,ans,bo[MAXN],g[MAXN];
void run()
{
ans=0;
memset(boy,0,sizeof(boy));
memset(girl,0,sizeof(girl));
cin>>a>>b>>k;
for(int i=0;i<k;i++)
{
cin>>bo[i];
boy[bo[i]]++;
}
for(int i=0;i<k;i++)
{
cin>>g[i];
girl[g[i]]++;
}
for(int i=0;i<k;i++)
{
int t1=bo[i],t2=g[i];
ans+=(k-i-1)-(boy[t1]+girl[t2]-2);
boy[t1]--,girl[t2]--;
}
cout<<ans<<endl;
}
signed main()
{
int t;
cin>>t;
while(t--) run();
}