欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

整理货架(模拟/思维)

程序员文章站 2022-04-07 19:08:48
...

整理货架(模拟/思维)

思路:

解法1:
因为数据范围较小,所以直接模拟即可。

解法2:
对于每一个位置,需要输出的次数T是需要向左边输出的次数加上需要向右边输出的次数(我用了前缀和计算),
因为题目说了一次操作可以选择任意数量的单元进行移动,所以对T取max就是答案

code(解法2):

#include<bits/stdc++.h>
using namespace std;
const int maxm=105;
int a[maxm];
int sum[maxm];
signed main(){
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        int tot=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            tot+=a[i];
        }
        if(tot%n){
            cout<<-1<<endl;
            continue;
        }
        int av=tot/n;
        for(int i=1;i<=n;i++){
            sum[i]=sum[i-1]+av-a[i];
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            int t=0;
            if(sum[i-1]>0)t+=sum[i-1];
            if(sum[n]-sum[i]>0)t+=sum[n]-sum[i];
            ans=max(ans,t);
        }
        cout<<ans<<endl;
    }
    return 0;
}
//http://oj.ecustacm.cn/problem.php?id=2003