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

LouisYuan · 2025-11-11 19:51:50 · 算法·理论

题意

有一个变量 s，初始为 0。现在有 n 个数字，每个数字可以对 s 做出如下变化：

• 如果 s 不比当前判断数字小，s 加 1；
• 否则，s 减 1。

找出 s 经过 n 次变化以后的最大值和最小值。

思路

看起来挺复杂的，但当我们看完样例以后发现，这种方案其实就是需要进行排序。样例还怕我们想复杂，特意加了最后一句的方法。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5 ; //n 很大，所以定义一个常数变量。
int n , a[N] ;
long long s;
//最坏情况为 10 的 5 次方乘上 10 的 5 次方，为 10 的 10 次方，需要开 long long。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //处理输入。
    cin >> n ;
    for(int i = 1 ; i <= n ; i++) cin >> a[i] ;
    //进行排序。
    sort(a + 1 , a + 1 + n);
    //求出最大值。
    for(int i = 1 ; i <= n ; i++){
        if(s >= a[i]) s++;
        else s--;
    }
    cout << s << " " ;
    s = 0 ;
    //求出最小值。
    for(int i = n ; i > 0 ; i--){
        if(s >= a[i]) s++;
        else s--;
    }
    cout << s << endl ;

    return 0;
}

如果您喜欢这篇题解，麻烦您点个赞，使这篇题解排名上升，谢谢！

（被打回）