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

NewOJ 问题 D: 整理货架(思维)

程序员文章站 2024-03-18 22:42:52
...

题目链接:点击这里
NewOJ 问题 D: 整理货架(思维)
NewOJ 问题 D: 整理货架(思维)

再给几个样例:

  • 0 4 0 4
  • 0 0 4 4
  • 4 0 0 4

题解原话(tcl):

  • 我是没想到这题居然没几个人过。。。

  • 对于每单元的货架,只需要考虑需要向两侧一共送出多少件货物即可。左右两侧视为一个整体即可。

  • 取(每一单元)送出货物件数的最大值。

#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<climits>

using namespace std;
typedef long long ll;
const int MOD = 10000007;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int maxn = 10010;
int t, n, ave, a[maxn], sum[maxn];

int main()
{
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d", &n);
		
		for(int i = 1; i <= n; ++i)
		{
			scanf("%d", &a[i]);
			sum[i] = sum[i-1] + a[i];
		}

		if(sum[n]%n!=0)		//不能达到经理的要求
		{
			printf("-1\n");
			continue;
		}
		
		ave = sum[n]/n;		//每个单元平均的货物,也就是每个单元应该放的货物

		
		int ans = INT_MIN;
		for(int i = 1; i <= n; ++i)
		{
			int left = ave*(i-1) - (sum[i-1]-sum[0]);
			if(left<0)	left = 0;
			
			int right = ave*(n-i) - (sum[n]-sum[i]);
			if(right<0)	right = 0;
			
			ans = max(ans, left+right);
		}
		
		printf("%d\n", ans);
	}
	return 0;
}
相关标签: 思维