Think:
求最多能买的大米,所以用贪心算法。。。背景题目太长,所以直接发输入输出的部分。
Input
输入数据首先包含一个正整数C,表示有C组测试用例,每组测试用例的第一行是两个整数n和m(0 < n <= 1000, 0 < m <= 1000 ),分别表示经费的金额和大米的种类,然后是m行数据,每行包含2个整数p和h(1 <= p <= 25,1 <= h <= 100),分别表示单价和对应大米的重量。
Output
对于每组测试数据,请输出能够购买大米的最多重量(你可以假设经费买不光所有的大米)。
每个实例的输出占一行,保留2位小数。
Example Input
1
7 2
3 3
4 4
Example Output
2.33
#include<stdio.h>#include<string.h>struct node{double wi;double pi;}a[1050], temp;int main(){int t, i, j, n;double p, h;while(scanf("%d",&n)!=EOF){for (t = 1;t <= n;t ++){double sum = 0;scanf("%lf %lf",&p, &h);for (i = 0;i <= h - 1;i ++){scanf("%lf %lf",&a[i].pi,&a[i].wi);}for (i = 0;i <= h - 1;i ++){for (j = 0;j <= h - 1;j ++){if (a[i].pi < a[j].pi){temp = a[i];a[i] = a[j];a[j] = temp;}}}i = 0;while(p){if (p >= a[i].pi){p = p - a[i].pi;sum = sum + 1;a[i].wi = a[i].wi - 1;}if (a[i].wi == 0)i = i + 1;if (p < a[i].pi){sum = sum + p / a[i].pi;p = 0;}}printf("%.2lf\n",sum);}}return 0;}/***************************************************User name: Result: AcceptedTake time: 0msTake Memory: 120KBSubmit time: -12-04 10:02:44****************************************************/
如果觉得《HDU2187悼念512汶川大地震遇难同胞》对你有帮助,请点赞、收藏,并留下你的观点哦!