本文主要是介绍uva 10670 Work Reduction(贪心)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
我就知道肯定能A,但凡觉得浪费了好长时间的时候都会去认真做一些事情，这道题目，亦如是，从我认真读题开始压
根没想着找题解看题意看思路。其实这道题目也算不上难，通过率有百分之四十。以后都得这样专心读题目，专心想解法。
思路：
贪心，关键是选择A方案还是B方案，A方案是每次代理一份作业花费n，B方案是每次代理一般方案（若16
或17，则代理8个）花费m，其实这道题能判断出来什么时候该选哪个方案就基本上解决了。只有当代理一般后不小
于目标的分数且比用A方案代理一半所花费的更少时才选用B方案，否则都应该选用A方案。这里似乎简单一些了，目
标是一个定值必须最终达到这个值。然后我竟然是第一次用结构体里面写数组，赋值，输出。。。好了，既然写过以
后就应该会了。。
贴代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<algorithm>using namespace std;
struct node
{char a[20];//记录字母 int m,n;int cost;
}b[105];
int cmp(const void *a,const void *b)
{if(((node *)a)->cost == ((node *)b)->cost)return strcmp(((node *)a)->a,((node *)b)->a);return ((node *)a)->cost - ((node *)b)->cost;
}int main()
{int T,x,y,i,j,k;char ch;cin >> T;int cnt = 0;while(T--){cnt++;cin >> x >> y >> k;//getchar();memset(b,0,sizeof(b));for(i=1; i<=k; i++){j = 0;getchar();//必须有，处理掉缓冲区的换行符 while(ch = getchar(), ch != ':'){b[i].a[j++] = ch;//注意结构体内a数组的输入 }b[i].a[j] = '\0';//不能忘，得给字符数组加结束标志 scanf("%d,%d",&b[i].n,&b[i].m);}// cout<<"********************\n";
/* for(i=1; i<=k; i++){cout << b[i].a << ": ";cout << "m = " << b[i].m << " " <<"n = " << b[i].n<<endl;}
*/ //cout<<"********************\n";int xx , yy;for(i=1; i<=k; i++){xx = x, yy = y;while(xx != 0){if((xx/2 >= yy)&&((xx-xx/2)*b[i].n>=b[i].m)){xx = xx/2;b[i].cost += b[i].m;}else {b[i].cost += (xx-yy)*b[i].n;xx = 0;}}}qsort(b+1,k,sizeof(b[0]),cmp);// cout<<"********************\n";/*for(i=1; i<=k; i++){cout << b[i].a << ": ";cout << "cost = " << b[i].cost << endl;}*///cout<<"********************\n";cout << "Case " << cnt << endl;for(i=1; i<=k; i++){cout << b[i].a << " " << b[i].cost<<endl;//注意结构体内a数组的输出 }} return 0;
}
这篇关于uva 10670 Work Reduction(贪心)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
