首页 > 代码库 > sgu-207 Robbers

sgu-207 Robbers

题目大意:

n个强盗抢银行共得到m个金币,抢劫前他们确定了分配方案,每个人按比例xi/Y分配,x1+x2+。。。+xn=Y,m不一定被Y整除,假设第i个强盗分配了ki个金币,那么不公平度为| xi/Y-ki/m |,现在输入n,m,y,x,求出ki,使得不公平度最小。


解题思路:

首先我们比例 [xi/Y*m] 给每个分配,然后由于是向下取整,所以分配出去的一定小于等于m,假设剩下了g个,那么此时我们把每个人分配的金币加1后的不公平度从小到大排序,然后将前g小的人的金币数加1,然后就行了



AC代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)>(b)?(b):(a))

using namespace std;
int n,m,y;
int x[1010]={0};
double t[1010]={0};
int a[1010]={0};
int rank[1010]={0};

bool cmp(int a1,int a2)
{
	double k1=fabs(t[a1]-(double)(a[a1]+1)*1.0/m);
	double k2=fabs(t[a2]-(double)(a[a2]+1)*1.0/m);
	if(k1<k2) return true;
	return false;
}

int main()
{
	int g;
	scanf("%d%d%d",&n,&m,&y);
	g=m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x[i]);
		t[i]=(double)x[i]*1.0/y;
		a[i]=m*x[i]/y;
		rank[i]=i;
		g-=a[i];
	}
	
	sort(rank+1,rank+n+1,cmp);
	
	for(int i=1;i<=g;i++)
		a[rank[i]]++;
	
	for(int i=1;i<=n;i++)
		printf("%d ",a[i]);

	return 0;
}


sgu-207 Robbers