修改时间: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}\),与排序矛盾。
代码实现
#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;
}
如果您觉得内容对您有用,请点个赞!
标签:cnt,Balls,数字,int,题解,位置,第二个,Revisited,排序 From: https://www.cnblogs.com/PlayWithCPP/p/17399267.html