AT_abc027_b题解

说明

需要掌握贪心算法。

这么简单为什么是黄题啊？

题意

给定一个长度为的非负整数序列，你可以进行若干次操作，每次操作都可以选择一个长度为的子串，花费的代价，将其中的每个数都变成该子串的平均值，现在你必须将每个数都变成相同的，你必须同时保证每个数为非负整数。

分析

先算出平均数，再把输出为或的特判掉，然后遍历一遍序列，考虑贪心，一旦遇到能够刚好平均的子串，就记录下代价，直至结束。

 代码

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],sum,aver,ans,t,t1;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    if(sum%n!=0)//判断无解
    {
        cout<<-1<<endl;
        return 0;
    }
    if(sum==0)//特判全是0的情况
    {
        cout<<0<<endl;
        return 0;
    }
    aver=sum/n;//算平均数
    for(int i=0;i<n;i++)
    {
        t+=a[i];
        t1++;
        if(t%aver==0&&t!=0&&t/aver==t1)//贪心
        {
            t=0;
            t1=0;
            continue;
        }
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}