AC_Dream 1224 Robbers（贪心）

题意：n个抢劫犯分别抢到的金钱是k1, k2, k3,...，一共得到的金钱是m，
但是在分钱的时候是按照x1/y, x2/y, x3/y,....的比例进行分配的！这样的话
一些抢劫犯就会觉得不公平，不公平度为|xi/y - ki/m|(浮点运算)， 输出一个序列ki，使得
总的不公平度最小.....

思路：很明显的贪心！ 首先按照 [xi/y](取整)的比例将每一个人得到的钱求出来(ni)，然后会得到
剩下的钱数, 最后在所有人中找到谁分配的相对比例少了，也就是xi/y*m - ni的最大值！找到这个人

之后，将他得到的钱数加 1！

#include iostream 

#include cstdio 

#include cstring 

#define N 1006

using namespace std;

int num[N];

int x[N];

bool flag[N];

int main(){

 int n, m, y;

 while(scanf("%d%d%d", n, m, y) != EOF){

 memset(flag, 0, sizeof(flag));

 int left = 0;

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

 scanf("%d", x[i]);

 num[i] = x[i]*m/y;

 left += num[i];

 if( x[i]%y == 0 ) flag[i] = true;

 left = m - left;

 while(left 0){

 double tmp = 0.0;

 int p = 0;

 for(int i=1; i ++i)

 if(tmp x[i]*1.0/y * m - num[i]){

 tmp = x[i]*1.0/y * m - num[i];

 p = i;

 --left;

 ++num[p];

 printf("%d", num[1]);

 for(int i=2; i ++i)

 printf(" %d", num[i]);

 printf("\n");

 return 0;

}

[USACO 2012 Feb G]Cow Coupons----贪心&带悔(看完稳AC) 意思是有n头牛，现在有k张优惠券以及m元，每头牛有一个原始价格和折扣价格，问最多能买多少牛 一开始的方法很简单，由于题目里面说了折扣价格一定比原始价格便宜，所以说首先按照折扣价格从小大大进行排序，将前k个牛的花费看作是折扣之后的价格，而将后面的花费看作是原始价格，然后重新将价值从小到大进行排序，尽可能的多选