题解：P14453 [ICPC 2025 Xi'an R] Grand Voting

· · 题解

题目传送门

1 具体做法

1.1 最大值

因为如果票数相对于 a_i 比较大，那么票数就能加一。所以我们可以先将 a 数组从小到大排序，再按顺序遍历，如果无法将票数增加那就放到最后处理，这样就不会因为再前面减少了票数而影响结果。

1.2 最小值

同上，因为如果票数相对于 a_i 比较小，那么票数就能减一。所以我们可以先将 a 数组从大到小排序，再按顺序遍历，如果无法将票数减少那就放到最后处理，这样就不会因为再前面增加了票数而影响最后的结果。

2 代码

2.1 最大值

实际上，我们并不需要改变 a 数组的顺序，只需要统计所有无法将票数增加的人数即可。

sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
    if(s>=a[i])s++;
    else x++;
}
cout<<s-x<<" ";

2.2 最小值

同上，我们并不需要改变 a 数组的顺序，只需要统计所有无法将票数减少的人数即可。

for(int i=n;i>=1;i--)
{
    if(s<a[i])s--;
    else x++;
}
cout<<s+x;

2.3 ACcode

#include<bits/stdc++.h>
using namespace std;
int n,s,x,a[10005];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a,a+n);
    for(int i=1;i<=n;i++)
    {
        if(s>=a[i])s++;
        else x++;
    }
    cout<<s-x<<" ";
    for(int i=n;i>=1;i--)
    {
        if(s<a[i])s--;
        else x++;
    }
    cout<<s+x;
    return 0;
}

已做防伪处理，请勿复制！！！