http://acm.hdu.edu.cn/showproblem.php?pid=2187
C++版本一
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int t;
int n,m;
int a[1100][2];
int main()
{
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d",&a[i][0],&a[i][1]);
}
int k;
for(int i=0;i<n;i++){
k=i;
for(int j=i+1;j<n;j++){
if(a[k][0]>a[j][0])
k=j;
}
if(k!=i){
long temp;
temp=a[k][0];
a[k][0]=a[i][0];
a[i][0]=temp;
temp=a[k][1];
a[k][1]=a[i][1];
a[i][1]=temp;
}
}
float ans=0;
float t=n;
for(int i=0;i<n;i++){
if(t<=0) break;
if(t>=a[i][1]*a[i][0]){
ans+=a[i][1];
t=t-a[i][1]*a[i][0];
}
else{
ans=ans+t/a[i][0];
break;
}
}
printf("%.2f\n",ans);
}
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
double p;
double h;
}a[1010];
bool cmp(node a,node b){
return a.p<b.p;
}
int main(){
int C; scanf("%d",&C);
while(C--){
double sum=0;
double n;
int m;
scanf("%lf %d",&n,&m);
for(int i=0;i<m;i++)
scanf("%lf%lf",&a[i].p,&a[i].h);
sort(a,a+m,cmp);
int i=0;
while(n>a[i].p){
while(a[i].h){
sum++;n-=a[i].p;a[i].h--;
if(n<a[i].p)
break;
}//先买到便宜的大米 判断是否卖完
if(n<a[i].p&&a[i].h)
break;
i++;
}
sum+=n/a[i].p;//剩余不够的买一斤大米的钱所买的大米数
printf("%.2lf\n",sum);
}
return 0;
}