题解：CF2111C Equal Values

题意

给定一个包含

n

个整数的数组，每次操作：

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

思路

目标值 $x$ 应为数组中的最小值，减少总成本。
对于最小值 $x$ 的最左边出现位置，用操作 $1$ 覆盖左边元素；最右边出现位置，使用操作 $2$ 覆盖右边元素。
$x$ 出现多次，中间已覆盖，不需要操作。只用检查是未被覆盖的，并进行补充操作。

代码

CPP

#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;
}

题解：CF2111C Equal Values

文章操作

题意

思路

代码

相关推荐

评论

题解：CF2111C Equal Values