杭电1009 http://acm.hdu.edu.cn/showproblem.php?pid=1009
题目大意：
一只肥鼠一开始有M个猫粮，经过N个房间。在每个房间，它可以用F[i]*a%的猫粮去换取J[i]*a%的鼠粮。
由于物品可分割，不能使用背包。
直接贪心，用结构体构造，按照Rate = f / j 这样的最大比例去排序，依次拾取即可。
AC代码：
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <cmath>
#include <stack>
#include <stdlib.h>
//#define DEBUG
using namespace std;
typedef long long ll;
double m;
int n;
struct p{double j;double f;double rate;
}pp[1005];
bool cmp(p a,p b) { //结构体构造排序if(a.rate==b.rate) return a.f<=b.f;return a.rate>b.rate;
}
int main() {while(cin>>m>>n) {if(m==-1&&n==-1) return 0;memset(pp,0, sizeof(pp));for(int i=0;i<n;i++) {cin>>pp[i].j>>pp[i].f;pp[i].rate=pp[i].j/pp[i].f;}sort(pp,pp+n,cmp);double sum=0;for(int i=0;i<n;i++) {if(m>=pp[i].f) { //整取sum+=pp[i].j;m-=pp[i].f;}else if(m>0&&m<pp[i].f) { //分取sum+=pp[i].j* (m/pp[i].f);break;}}printf("%.3lf\n",sum);}return 0;
}