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

· · 题解

思路

贪心，不过要分情况讨论。

  1. 最大值：根据题意，很明显，我们要尽量先选小的，这样票数才能加上去。
  2. 最小值：相反的，我们尽量先选大的，这样票数才能减下去。

所以根据两种情况，我们要先从小到大排序，处理最大值。再从大到小排序，处理最小值。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],minn,maxn;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){ //处理最大值
        if(maxn>=a[i]) maxn++;
        else maxn--;
    }
    reverse(a+1,a+n+1); //将从小到大的数组倒过来，就是从大到小的数组
    for(int i=1;i<=n;i++){ //处理最小值
        if(minn<a[i]) minn--;
        else minn++;
    }
    cout<<maxn<<' '<<minn;
    return 0;
}