题解：CF2111C Equal Values

· · 题解

题意

给定一个包含 n 个整数的数组，每次操作：

  1. 选位置 i(1<i≤ n)，将左侧所有元素设为 a_i，成本为 (i-1)・a_i；
  2. 选位置 i(1≤i<n)，将右侧所有元素设为 a_i，成本为 (n-i)・a_i。
    求使数组所有元素相等的最小总成本。

    思路

    • 目标值 x 应为数组中的最小值，减少总成本。
    • 对于最小值 x 的最左边出现位置，用操作 1 覆盖左边元素；最右边出现位置，使用操作 2 覆盖右边元素。

代码

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n;cin>>n;
    vector<int>a(n);
    for(int&x:a)cin>>x;
    int mn=*min_element(a.begin(),a.end());
    vector<int>pos;
    for(int i=0;i<n;++i)if(a[i]==mn)pos.push_back(i);
    long long res=(long long)pos[0]*mn+(long long)(n-1-pos.back())*mn;
    for(int i=1;i<pos.size();++i)res+=(long long)(pos[i]-pos[i-1]-1)*mn;
    cout<<res<<'\n';
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t;cin>>t;
    while(t--)solve();
return 0;
}