B4274 数字游戏题解

noip_1 · 2025-05-10 21:22:42 · 题解

B4274 数字游戏

1. 思路分析

题目大意：

进行若干次操作，第一次将 1 个最大值变为次大值，第二次将 1 个最小值变为次小值，直到不同的数少于 3 个时，输出操作次数、剩下最大值和剩下最小值。

由于数字会重复出现，我们可以同时改变多个最大值和最小值代替模拟一次次操作，以此减轻时间复杂度。

2. 时间复杂度分析

最坏情况：当 N=10^6 ，且每一个数不一样，每次同时改变 1 个最大值和 1 个最小值，需要操作 \frac{N-2}{2}=499,999 次，不难看出时间复杂度为 O(n) ，简直完美。

3. 代码细节

由于题目优先改变最大值，所以要注意当仅有 1 个最大值和 2 种不同的数时，无需同时与最小值一起改变，只需单独改变最大值即可。（详情见代码特判部分）
十年 OI 一场空，不开 long long 见祖宗。当 N=10^6 且每一个数不一样时，答案约为 2\sum_{i=1}^{\frac{N-2}{2}}i=2\times\frac{(5\times 10^5-1)\times5\times10^5}{2} =25\times10^{10}-5\times10^5
明显超过 int 类型的最大值 2^{31}-1 即 2147483647 ，所以使用 long long 存答案。

代码:

#include<bits/stdc++.h>
#define int long long //无脑 long long 太爽了
using namespace std;
const int N = 1e6+5;
int n, m, idx, ans, vis[N];
struct node{
    //x为数值 t为次数的出现次数
    int x, t;
} a[N];
signed main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> m;
        vis[m]++; //同标记出现次数
    }
    for(int i = 1; i <= 1e6; i++){
        //用vis数组维护a
        if(vis[i]) idx++, a[idx].x = i, a[idx].t = vis[i];
    }
    int l = 1, r = idx;
    while(r-l+1 >= 3){
        int tmp = min(a[l].t, a[r].t); //取左右出现次数最小值
        a[l].t -= tmp, a[l+1].t += tmp, ans += tmp; //左边减去最小值，并维护ans
        if(a[l].t == 0){ //当 a[l].t > a[r].t 时减去剩余的
            l++;
            if(r-l+1 < 3){//特判
                ans+= tmp-1;
                break;
            }
        }
        //右边同理
        a[r].t -= tmp, a[r-1].t += tmp, ans += tmp;
        if(a[r].t == 0){
            r--;
            if(r-l+1 < 3) break;
        }
    }
    cout << ans << ' ' << a[l].x << ' ' << a[r].x; //输出答案，收工~
    return 0;
}

B4274 数字游戏 题解