P4016 负载平衡问题

本文主要是介绍P4016 负载平衡问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目描述

G 公司有 n 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 nn 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。

输入格式

第一行一个正整数 nn，表示有 n 个仓库。

第二行 n 个正整数，表示 n 个仓库的库存量。

输出格式

输出最少搬运量。

输入输出样例

5
17 9 14 16 4

11

说明/提示

1≤n≤100。

方法一：

https://www.cnblogs.com/five20/p/8869948.html

数学+贪心

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,a[104];
 4 int s[104];
 5 int main()
 6 {
 7     cin>>n;
 8     int sum=0;
 9     for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
10     sum/=n;
11     for(int i=1;i<=n;i++)a[i]-=sum,s[i]=s[i-1]+a[i];
12     sort(s+1,s+1+n);//找中位数
13     int t=s[n/2+1];
14     int ans=0;
15     for(int i=1;i<=n;i++)ans+=abs(t-s[i]);
16     cout<<ans<<endl;
17 }

这篇关于P4016 负载平衡问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！