poj 1907 Work Reduction_贪心

题意：公司要你要完成N份任务，但是你是不可能全部完成的，所以需要雇佣别人来做，做到剩下M份时，自己再亲自出马。现在有个机构，有两种付费方式，第一种是每付A元帮你完成1份，第二种是每付B元帮你完成剩下任务的一半（rounding down）。

思路： 先算出每个的最少费用然后排序就行了，要注意的是当费用相等时，按名字的字典序排序

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100010
struct node{
	char name[110];
	int sum;
}p[N];
bool cmp(node a, node b){
	if(a.sum==b.sum)
		return strcmp(a.name,b.name)<0;
	return a.sum<b.sum;
}
int main(int argc, char** argv) {
	int t,a,b,n,m,l,i,j,tmp,u,cas=1;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&m,&l);
		for(i=0;i<l;i++){
			getchar();
			for(j=0;;j++){
				scanf("%c",&p[i].name[j]);
				if(p[i].name[j]==‘:‘){
					p[i].name[j]=‘\0‘;
					break;
				}
			}
			scanf("%d,%d",&a,&b);
			u=n;
			tmp=0;
			while(u/2>=m&&(u-u/2)*a>=b)
				u/=2,tmp+=b;
			p[i].sum=tmp+(u-m)*a;	
		}
		sort(p,p+l,cmp);
		printf("Case %d\n",cas++);
		for(i=0;i<l;i++)
			printf("%s %d\n",p[i].name,p[i].sum);
	}
	return 0;
}

poj 1907 Work Reduction_贪心,布布扣,bubuko.com

poj 1907 Work Reduction_贪心

原文：http://blog.csdn.net/neng18/article/details/20222531