题解：B4274 [蓝桥杯青少年组省赛 2023] 数字游戏 / [SNOW] - 11

fish_love_cat · 2026-01-24 01:21:11 · 题解

离散化用 map 是坏习惯，会被常数击败，改了能快十倍。

警钟长鸣。

考虑到变化是跳跃的，很烦，于是不妨先离散化了。

位置不连续很难看，反正这题和位置也没关系，不妨先排序。

模拟单次操作显然很笨，不妨对一类数放在一起进行消除。

于是把一类数字压在一起，用一个 pair 同时表示种类和数量。

开一个双端队列，显然操作的会是头尾。

不断分讨消除两端直到满足条件为止。

现在模拟题面即可，不用说了吧。

因为每次操作都会减少一类数，所以时间复杂度 O(n\log n)，瓶颈在于排序。

代码有点长。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1000005];
int mp[1000005];
int pm[1000005];
struct que{
    pair<int,int>qwq[1000005];
    int l=1,r=0;
    void push_back(pair<int,int>x){
        qwq[++r]=x;
    }
    void push_front(pair<int,int>x){
        qwq[--l]=x;
    }
    void pop_front(){
        l++;
    }
    void pop_back(){
        r--;
    }
    pair<int,int>front(){
        return qwq[l];
    }
    pair<int,int>back(){
        return qwq[r];
    }
    int size(){
        return r-l+1;
    }
};
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i],mp[a[i]]=1;
    int qwq=0;
    for(int i=1;i<=1000000;i++)
    if(mp[i])mp[i]=++qwq,pm[qwq]=i;
    for(int i=1;i<=n;i++)
    a[i]=mp[a[i]];
    sort(a+1,a+1+n);
    que q;
    int sum=1;
    for(int i=2;i<=n;i++){
        if(a[i]!=a[i-1]){
            q.push_back({sum,pm[a[i-1]]});
            sum=1;
        }else sum++;
    }
    if(sum)q.push_back({sum,pm[a[n]]});
    int ans=0;
    while(q.size()>2){
        if(q.front().first<q.back().first){
            int x=q.front().first;
            q.pop_front();
            pair<int,int>flc=q.front();
            q.pop_front();
            flc.first+=x;
            q.push_front(flc);
            ans+=2*x;
            if(q.size()==2)ans--,x--;
            flc=q.back();
            q.pop_back();
            flc.first-=x;
            pair<int,int>fis=q.back();
            q.pop_back();
            fis.first+=x;
            q.push_back(fis);
            q.push_back(flc);
        }else if(q.front().first==q.back().first){
            int x=q.front().first;
            q.pop_front();
            pair<int,int>flc=q.front();
            q.pop_front();
            flc.first+=x;
            q.push_front(flc);
            ans+=2*x;
            if(q.size()==2)ans--,x--;
            flc=q.back();
            q.pop_back();
            flc.first-=x;
            pair<int,int>fis=q.back();
            q.pop_back();
            fis.first+=x;
            q.push_back(fis);
            if(flc.first)
            q.push_back(flc);
        }else{
            int x=q.back().first;
            q.pop_back();
            pair<int,int>flc=q.back();
            q.pop_back();
            flc.first+=x;
            q.push_back(flc);
            ans+=2*x;
            flc=q.front();
            q.pop_front();
            flc.first-=x;
            pair<int,int>fis=q.front();
            q.pop_front();
            fis.first+=x;
            q.push_front(fis);
            q.push_front(flc);
        }
    }
    cout<<ans<<' '<<q.front().second<<' '<<q.back().second;
    return 0;
}
// 接著装满袋子后，她从口袋里拿出钱，投进——
//「……已经，不用投钱也没关系了吧。」

// 并没有投进箱中。

// 反正就算不投钱，结果也不会改变。
// 既然如此，能偷多少就偷多少吧。
// 这一定不是在做坏事。
// 我没有错。