CF1475C Ball in Berland
题意
在毕业典礼上,有\(a\)个男孩和\(b\)个女孩准备跳舞,不是所有的男孩和女孩都准备结伴跳舞。
现在你知道\(k\)个可能的舞伴,你需要选择其中的两对,以便使没有人重复地出现在舞伴里,求可能的数量。
思路
暴力
最朴素,也是简单的方法,就是通过暴力组合进行配对。
#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++;
}
}
那么,该怎么进行优化,使其从\(O(k)\)变为\(O(1)\)呢?
这段代码的用途其实就是在\(t1,t2\)后面查找有没有重复出现的人。关注题目中的数据范围:\(1 \leq t \leq 10^4,1\leq a,b,k \leq 2\cdot 10^5\),因此可以开一个桶来存储男生和女生各出现的次数,然后再与当前\(t1,t2\)作差即可
手玩一下样例:
最开始的桶是这样的:
boy | 2 | 1 | 1 | |
---|---|---|---|---|
girl | 0 | 2 | 1 | 1 |
随后,对\((1,2)\)进行判断,ans=剩余组数(\(3\))-重复数量(\(2-1+2-1\)),即\(ans=1\)
然后,桶变成了这样:
boy | 1 | 1 | 1 | |
---|---|---|---|---|
girl | 0 | 1 | 1 | 1 |
为了避免重复,每次计算完1组后都需要更新一下对应的男女生人数。进行完\((1,3)\)的操作后,\(ans=3\)
随后是这样:
boy | 0 | 1 | 1 | |
---|---|---|---|---|
girl | 0 | 1 | 0 | 1 |
继续进行如上操作,\(ans=4\),更新桶
接着:
boy | 0 | 0 | 1 | |
---|---|---|---|---|
girl | 0 | 0 | 0 | 1 |
当只剩1组时,意味着枚举结束了,并输出\(ans\)为\(4\)
整个程序的时间复杂度是\(O(5tk)\),CF的机子慢所以算精确点,不会超时
另:十年CF一场空,不开\(long\space long\)见祖宗
代码
#include<bits/stdc++.h>
#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();
}
标签:boy,Ball,run,Berland,int,CF1475C,ans,MAXN,girl
From: https://www.cnblogs.com/lyk2010/p/17852262.html