题解归档 - cf2224B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2224B
• 本地来源：problems/cf2224B/idea.md
• 题目链接：https://codeforces.com/contest/2224/problem/B
• 原始标题：cf2224B - Zhily and Mex and Max

思路

cf2224B - Zhily and Mex and Max

Pattern

Think of each prefix contribution as prefix_mex + prefix_max.

Claim

There is an optimal order with one global maximum M placed first. Then every
prefix has maximum M, so the total max contribution is exactly n*M.

After that, maximizing the mex contribution is independent: always place the
current missing mex value as early as possible if it exists. Duplicates and
values larger than the current mex do not help mex before the missing value is
placed.

The first M is already seen for mex purposes. This matters when the mex chain
reaches M, because it jumps over M.

Algorithm

1. Count frequencies of values up to n+1, and find global maximum M.
2. Mark M as already seen, because we put it first.
3. Add current mex for the first prefix.
4. While there are positions left and the current mex exists in the remaining
   multiset, place it, update seen/mex, and add the new mex.
5. If the current mex no longer exists, all remaining prefixes contribute the
   same mex.

Answer is n*M + mex_sum.

Complexity

O(n) per test case.

代码

来源：problems/cf2224B/solution.cpp

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

using ll=long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        vector<ll>a(n);
        ll mx=0;
        vector<int> freq(n+2,0);
        for(ll &x:a){
            cin>>x;
            mx=max(mx,x);
            if(x<=n+1) freq[(int)x]++;
        }
        vector<char> seen(n+2,0);
        if(mx<=n+1) seen[(int)mx]=1;
        int mex=0;
        while(mex<=n+1&&seen[mex]) mex++;
        ll mexSum=mex;
        int pos=1;
        while(pos<n){
            if(mex<=n+1&&freq[mex]>0){
                seen[mex]=1;
                pos++;
                while(mex<=n+1&&seen[mex]) mex++;
                mexSum+=mex;
            }else{
                mexSum+=1LL*(n-pos)*mex;
                break;
            }
        }
        cout<<1LL*n*mx+mexSum<<"\n";
    }
    return 0;
}