洛谷 [P4016] 负载平衡问题

贪心做法

第一眼看见觉得和均分纸牌差不多,然而因为这是环形的,并不能用均分纸牌的方法做,但是均分纸牌的思想仍然适用

首先我们假设平均数为sum1。

那么对于第1个人，我们假设他给第N个人K个糖果，

第2个人给1

第3个人给2

第n个人给第n-1个人

那么对于第1个人给完n，第2个人给完1，第一个人不会再改变糖果数了

所以应该是sum1那么第一个人原来是a1

给n之后是a1-k，代价是k，

第2个人给1，使1的糖果数是sum1，所以应该给sum1-a1+k个，代价是 $abs(sum1+k-a1)=abs(a1-k-sum1)$ ，那么第2个人变成了 $a2+a1-k-sum1$ 个

、第3个人需要给2个人 $sum1-a2-a1+k+sum1=2*sum1-a1-a2+k$ 个，那么代价是 $abs(2*sum1-a1-a2+k)=abs(a1+a2-k-2*sum1)$

以此类推第n个人给第n-1个人，代价应为 $abs((a1+a2+……+an-1)-k-(n-1)*sum1)$，

那么第一个人给第n个人的代价k可以看成$abs((a1+a2+……+an)-k-n*sum1)$，

所以我们设 $b[i]=Σ(a[j])-i*sum1 j<=i$ 那么 4max=Σ(b[i]-k)$

那么b[i]是定值，和k无关，我们可以求出来，

就是求max的最小值了，

那么k应该是b[i]数组中的中位数,用数轴判断

可以使max最小我们要找的就是sum的中位数，快排下就好了

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

int n,tot,num[105];

int main(){

	cin>>n;

	for(int i=1;i<=n;i++){

		cin>>num[i];

		tot+=num[i];

	}

	tot/=n;

	for(int i=1;i<=n;i++) num[i]+=num[i-1]-tot;

	sort(num+1,num+1+n);

	tot=n%2?num[n/2+1]:(num[n/2]+num[n/2+1])/2;

	int ans=0;

	for(int i=1;i<=n;i++) ans+=abs(num[i]-tot);

	cout<<ans<<endl;

	return 0;

}

网络流做法

最小费用最大流

转换成供求平衡问题,待续...

巴特西

洛谷 [P4016] 负载平衡问题

贪心做法

网络流做法

最新文章

热门文章