Ball in Berland - 洛谷
题意
在毕业典礼上,有个男孩和个女孩准备跳舞,不是所有的男孩和女孩都准备结伴跳舞。
现在你知道个可能的舞伴,你需要选择其中的两对,以便使没有人重复地出现在舞伴里,求可能的数量。
思路
最朴素,也是简单的方法,就是通过暴力组合进行配对。
然而,会在第四个点超时,所以还得优化
利用桶进行优化
我们注意到,超时的原因就是这段代码:
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一场空,不开见祖宗
代码