CF1728A Colored Balls: Revisited题解

[去我的Blog观看](https://www.luogu.com.cn/blog/SunnyYuan/solution-cf1728a) **修改时间：2022/9/11修改了格式与标点** **修改时间：2022/9/13修改了个别不严谨的语句** ### 题目大意 有 $n$ 种颜色的球，颜色为 $i$ 的球为 $cnt_i$ 个（$cnt_1+cnt_2+\dots+cnt_n$ 为奇数）。每次从球堆中取出 $2$ 个颜色不相同的球，问最后可能剩下哪种颜色的球（输出任意一种即可）。 ### 题目分析 其实只要找出序列中**最大值**所在位置 $i$ 即可，那就是最后剩下的一**种**球。 ### 理论证明（可以不看） 将 $cnt$ 数组从小到大排序，先同时拿排在第一个位置和第二个位置的球，直到第一个位置**没有球**了（也就是排序后的第一个颜色被拿完了）。 此时第二个位置应该还有球，再同时拿第二个位置和第三个位置的球，直到第二个位置**没有球**了。 第三个位置应该还有球。 以此类推，最后在第 $n-1$ 个位置的球拿完时，第 $n$ 个位置的球一定是唯一的一种颜色的球。 ### 常见问题 ##### Q1：如果只有两个数字且个数相同怎么办？ ##### A1：那它们的和为偶数违背了题意（$cnt_1+cnt_2+\dots+cnt_n$ 为奇数）。 ##### Q2：会不会到最后两个位置时，它们的数字相同？ ##### A2：不可能。因为在两个数字的时候不成立(已证明)。那在多个数字的时候，第 $n-1$ 个数字已经和第 $n-2$ 个数字消掉一部分了，如果此时 $cnt_{n-1}=cnt_{n-2}$，那么原先的 $cnt_{n-1}$ 一定大于 $cnt_{n-2}$，与排序矛盾。 ### 代码实现 ```cpp #include <bits/stdc++.h> using namespace std; const int N=25; //最大个数为25个 int T,n; //数据组数与数据个数 int a[N]; //存放数字 void solve() { int color_max=1; //记录最大值的那一位 scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=2;i<=n;i++) if(a[color_max]<a[i])//如果当前值比最大值还要大，更新最大值 color_max=i; printf("%d\n",color_max);//输出最大值所在位置 } int main() { scanf("%d",&T); while(T--)solve(); return 0; } ``` [看看效率如何](https://www.luogu.com.cn/record/86153037) 如果您觉得内容对您有用，请点个赞!