悼念512汶川大地震遇难同胞——老人是真饿了 |
| Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) |
| Total Submission(s): 1376 Accepted Submission(s): 580 |
| Problem Description 时间：5008年5月16日（震后第4天） 地点：汶川县牛脑寨 人物：羌族老奶奶 【转载整理】牛脑寨是一个全村600多人的羌族寨子，震后几天，这里依然能常常听到隆隆的声音，那是对面山上石头不断滑落的声音。在完成整个突击队的抢修移动基站的任务后，我提着相机开始记录这里的受创情况。 突然，我的视线里出现一个羌族老人，这让我无比的震惊，要知道，那是一个极陡的坡，这个佝偻着腰的老人是怎么艰难地爬上来的？她上来做什么？     |
| Input 输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m（0<n<=1000,0<m& lt;=1000）,分别表示经费的金额和大米的种类，然后是m行数据，每行包含2个整数p和h(1<=p<=25,1<=h& lt;=100)，分别表示单价和对应大米的重量。 |
| Output 对于每组测试数据，请输出能够购买大米的最多重量（你可以假设经费买不光所有的大米）。 每个实例的输出占一行，保留2位小数。 |
| Sample Input 17 23 34 4 |
| Sample Output 2.33 |
| Author lcy |
| Source 2008-06-18《 ACM程序设计》期末考试——四川加油！中国加油！ |
| Recommend lcy |
基于快速排序，先对单价进行排序，重量随着单价的变动而变动。然后，通过比较（剩余金额/大米）与此种大米重量的大小，决定是否继续下去，其间用一个变量记录重量的变化。
#include<iostream>
#include<stdio.h>using namespace std;void quicksort(int list1[],int list2[],int a,int b){ if(a<b) { int first,last,compare,tem; first=a; last=b; compare=list1[a]; tem=list2[a]; while(a<b) { while(a<b&&list1[b]>=compare) b--; if(a<b) { list1[a]=list1[b]; list2[a]=list2[b]; a++; } while(a<b&&list1[a]<compare) a++; if(a<b) { list1[b]=list1[a]; list2[b]=list2[a]; b--; } } list1[a]=compare; list2[a]=tem; quicksort(list1,list2,first,a-1); quicksort(list1,list2,a+1,last); }}int main(){ int c,i,m; int v[1000],w[1000]; double n,weight; cin>>c; while(c--) { weight=0; cin>>n>>m; for(i=0;i<m;i++) cin>>v[i]>>w[i]; quicksort(v,w,0,m-1); for(i=0;i<m;i++) { if(w[i]<=n/v[i]) { n=n-v[i]*w[i]; weight=weight+w[i]; } else { weight=weight+n/v[i]; break; } } printf("%.2f\n",weight); } return 0;}