首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。