好贷网好贷款

uva 10670 Work Reduction

发布时间:2016-12-3 10:22:30 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"uva 10670 Work Reduction",主要涉及到uva 10670 Work Reduction方面的内容,对于uva 10670 Work Reduction感兴趣的同学可以参考一下。

题意:有N个任务,求在完成的只剩M个的时候花费最少的方法,坑的地方是rounding down是向下取整的意思,至于方法的选择只要采用贪心就行了,对比一下两种花费就可以了 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 105; struct node { char name[30]; int A,B; int cost; }arr[MAXN]; int N,M,L; bool cmp(node a,node b) { if (a.cost != b.cost) return a.cost < b.cost; return strcmp(a.name,b.name) < 0; } int main() { int t,cas = 1; scanf("%d",&t); while (t--) { char str[30]; scanf("%d%d%d",&N,&M,&L); for (int i = 0; i < L; i++) { scanf("%s",str); int j; for (j = 0; str[j] != ':'; j++) arr[i].name[j] = str[j]; arr[i].name[j] = '\0'; sscanf(str+j+1,"%d,%d",&arr[i].A,&arr[i].B); arr[i].cost = 0; } for (int i = 0; i < L; i++) { int cur = N; int A = arr[i].A,B = arr[i].B; int half = (cur + 1) / 2; while (cur - half >= M && B <= half * A) { arr[i].cost += B; cur -= half; half = (cur + 1) / 2; } if (cur > M) arr[i].cost += (cur - M) * A; } sort(arr,arr+L,cmp); printf("Case %d\n",cas++); for (int i = 0; i < L; i++) printf("%s %d\n",arr[i].name,arr[i].cost); } return 0; }

上一篇:CEGUI 输入法窗口实现
下一篇:定义指向模板函数的函数指针类型

相关文章

相关评论