题解：P12842 [蓝桥杯 2025 国 A] 土地整平计划

· · 题解

P12842 [蓝桥杯 2025 国 A] 土地整平计划 题解

题目传送门

题意

给定一个长度为 n 的数列 h，可以做这样的若干次操作：

  1. 如果把区间 [1,r] 修改成 h_{r+1}，需满足区间内所有元素不与 h_{r+1} 相同，花费 h_{r+1}。
  2. 如果把区间 [l,n] 修改成 h_{l-1}，需满足区间内所有元素不与 h_{l-1} 相同，花费 h_{l-1}。
  3. 如果把区间 [l,r] 修改成 h_{l-1}，需满足 h_{l-1}=h_{r+1} 且区间内所有元素不与 h_{l-1} 相同，花费 h_{l-1}。

问要将这个序列的元素变成全部相等的，最少要操作多少次。

思路

先特判所有元素本来就一样的情况。

然后维护一个桶 cnt 记录花费为 cnt_i 时要修改几个区间（几次），具体操作为：

  1. 将所有 cnt_{h_i} 都设为一，因为 h_i 的出现次数要加一才是操作次数，先把每一个都变成一，后面就不用加一了。
  2. 将 h_i \neq h_{i-1} 的 cnt_{h_i} 加一，开始统计 h_i 的出现次数。
  3. 将 cnt_{h_1} 和 cnt_{h_n} 减一，因为 h_1 和 h_n 会被多记一次，所以才需要减一；

知道了 cnt_i(i \in [\min{h_i},\max{h_i}])，每个 i 的答案就显而易见了，即 cnt_i \times i。在所有 i 里取最小的，即为本题的答案。

时空复杂度

代码

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

int const N=1e6+10;
int n,an[N],flag,L,R,cnt[N],ans=INT_MAX;

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>an[i];
        L=min(L,an[i]),R=max(R,an[i]);
        if(!cnt[an[i]]) flag++;
        cnt[an[i]]=1;
    }
    if(flag==1){
        cout<<0;
        return ;
    }
    for(int i=1;i<=n;i++){
        if(an[i]!=an[i-1])  cnt[an[i]]++;
    }
    cnt[an[1]]--,cnt[an[n]]--;
    for(int i=L;i<=R;i++){
        if(cnt[i])  ans=min(ans,cnt[i]*i);
    }
    cout<<ans;
    return ;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--) solve();
    return 0;
}