2013
11-26

# HDU 1009 FatMouse’ Trade-贪心-[解题报告] C++

FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.
The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.

The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1′s. All integers are not greater than 1000.

For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.

5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1

13.333
31.500

#include<stdio.h>
#include<algorithm>
struct node {
double j,f,velu;
}java[1000+5];
double M;
int N;
bool cmp(node a,node b) {
return a.velu>b.velu;
}
int main() {
while(scanf("%lf%d",&M,&N)&&!(M==-1||N==-1)) {
double sum=0;
for(int i=1;i<=N;++i) {
scanf("%lf%lf",&java[i].j,&java[i].f);
java[i].velu=1.0*java[i].j/java[i].f;
}
if(N>1)
std::sort(java+1,java+N+1,cmp);
for(int i=1;;++i) {
if(N==0)
break;
if(M>=java[i].f) {
M-=java[i].f;
sum+=java[i].j;
}
else{
sum+=1.0*M*java[i].j/java[i].f;
break;
}
}
printf("%.3lf\n",sum);
}
return 0;
}

2. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}

3. 站长，你好！
你创办的的网站非常好，为我们学习算法练习编程提供了一个很好的平台，我想给你提个小建议，就是要能把每道题目的难度标出来就好了，这样我们学习起来会有一个循序渐进的过程！