题解归档 - cf104114I

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

• 本地编号：cf104114I
• 本地来源：problems/cf104114I/idea.md
• 题目链接：https://codeforces.com/gym/104114/problem/I
• 原始标题：cf104114I - Inadequate Operation

思路

cf104114I - Inadequate Operation

View the process by horizontal layers.

For a fixed height h, positions with a[i] >= h need to be "covered" once by operations on adjacent pairs. One operation at level h covers the chosen edge's endpoints at this layer, and lower values being raised to h-1 do not matter for this layer.

So for each h, the minimum number of operations equals the minimum edge cover of the active vertices on a path. Active vertices form disjoint contiguous components; a component of length len needs ceil(len/2) adjacent edges (also true for len=1, covered by either neighboring edge since n>=2).

Sweep heights descending. Add positions when their value becomes active, maintain connected active components with DSU, and maintain

cur = sum ceil(component_length/2).

Between two consecutive distinct heights, cur is constant, so add cur * delta_height.

Complexity: O(n log n).

代码

来源：problems/cf104114I/solution.cpp

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

ll need(ll len){
    return (len+1)/2;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n;
    vector<ll>a(n);
    vector<pair<ll,int>> ord;
    ord.reserve(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(a[i]>0) ord.push_back({a[i],i});
    }
    sort(ord.rbegin(),ord.rend());

    vector<int> fa(n),sz(n,0),on(n,0);
    iota(fa.begin(),fa.end(),0);

    auto find=[&](auto self,int x)->int{
        return fa[x]==x?x:fa[x]=self(self,fa[x]);
    };

    ll cur=0,ans=0;

    auto unite=[&](int x,int y){
        int rx=find(find,x),ry=find(find,y);
        if(rx==ry) return;
        cur-=need(sz[rx]);
        cur-=need(sz[ry]);
        if(sz[rx]<sz[ry]) swap(rx,ry);
        fa[ry]=rx;
        sz[rx]+=sz[ry];
        cur+=need(sz[rx]);
    };

    ll last=ord.empty()?0:ord[0].first;
    for(int ptr=0;ptr<(int)ord.size();){
        ll h=ord[ptr].first;
        ans+=cur*(last-h);
        while(ptr<(int)ord.size()&&ord[ptr].first==h){
            int x=ord[ptr].second;
            on[x]=1;
            fa[x]=x;
            sz[x]=1;
            cur+=1;
            if(x&&on[x-1]) unite(x,x-1);
            if(x+1<n&&on[x+1]) unite(x,x+1);
            ptr++;
        }
        last=h;
    }
    ans+=cur*last;

    cout<<ans<<"\n";
    return 0;
}