loj #6013. 「网络流 24 题」负载平衡
2024-09-04 06:19:33
#6013. 「网络流 24 题」负载平衡
题目描述
G 公司有 n nn 个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等。如何用最少搬运量可以使 n nn 个仓库的库存数量相同。搬运货物时,只能在相邻的仓库之间搬运。
输入格式
文件的第 1 11 行中有 1 11 个正整数 n nn,表示有 n nn 个仓库。
第 2 22 行中有 n nn 个正整数,表示 n nn 个仓库的库存量。
输出格式
输出最少搬运量。
样例
样例输入
5
17 9 14 16 4
样例输出
11
数据范围与提示
1≤n≤100 1 \leq n \leq 1001≤n≤100
思路:首先求出平均数,因为物资流动的最终结果是每个仓库的货物数目相同,就是每个仓库货物数目达到平均数。
然后环形仓库可以向两边搬运,所以固定一个方向,就是a[i] - >a[i+1]吧,并记录搬运数量为c[i]。所以c[i]就表示货物由第i个仓库搬到第i+1仓库的数量,负数表示i+1仓库往第i个仓库搬货。然后根据a[i]+c[i]-c[i-1]==m,可以求出每个仓库的货物搬动数量。
接下来就是处理搬运货物的总量最小,就是∑|c[i]| (i=0…n-1)最小。拿回原题意语境中我们可以知道c[i] (i=0,1,2…n-1)是相互影响的,但是它们的相对大小不会改变,所以我们现在可以把问题转化为一个数学题,就是把c[i]固定在一个数轴上,然后确定一个原点,保证绝对值之和最小即可。
然后就可以发现将原点固定在c[0]-c[n]最中间的位置(物理位置中间,就是原点左右两边数目尽可能相同)时绝对值之和时最小的。因为c[i] (i=0,1,2…)是相互影响的,又因相对大小不会改变,所以我们可以把c[0]随便赋一个值,然后就可以把c[i]的相对值都求出来了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 110
using namespace std;
int a[maxn],c[maxn],n,m;
int main(){
long long sum=;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
sum+=a[i];
}
m=sum/n;
c[]=;
for(int i=;i<=n;i++)c[i]=c[i-]+a[i]-m;
sort(c+,c+n+);
int mn=;
for(int i=,j=n;i<j;i++,j--)mn+=c[j]-c[i];
printf("%d",mn);
return ;
}
最新文章
- 对百度WebUploader开源上传控件的二次封装,精简前端代码(两句代码搞定上传)
- CompoundButton.OnCheckedChangeListener与RadioGroup.OnCheckedChangeListener冲突
- sql 2012中获取表的信息,包含字段的描述
- HTML标签-【fieldset】-fieldset
- 怎样用SQL语句查询一个数据库中的所有表?
- asp.net各种cookie代码和解析
- java23种设计模式
- 【转】javascript运行机制之this详解
- 【分享】Maven插件的源码下载(SVN)
- MBR所在位置
- BZOJ2802: [Poi2012]Warehouse Store
- 【转】iOS-Core-Animation-Advanced-Techniques(一)
- 安装python3.4
- python文件操作_对文件进行复制拷贝_代码实现
- CICD - Teamcity 配置之一: 数据库自动部署
- 关于JS的一些案例,setInterval,动态图片
- linux系统中使用socket直接发送ARP数据
- Codeforces 576E Painting Edges [分治,并查集]
- 喜闻乐见-Android应用的生命周期
- Linux用户组相关指令
热门文章
- oracle语言基础
- scala中存在的问题
- 【bzoj2144】跳跳棋
- 345. Reverse Vowels of a String翻转字符串中的元音字母
- 在C语言中如何嵌入python脚本
- 使用mail架包发送邮件javax.mail.AuthenticationFailedException: failed to connect at javax.mail.Service.connec
- 第九课,ROS仿真1
- spark源码阅读之network(1)
- Monkey压力测试Android常见的错误类型及黑白名单的使用方法
- css总结6:行高和字体大小