M29949: 贪婪的哥布林

greedy, http://cs101.openjudge.cn/practice/29949/

#include<bits/stdc++.h>
using namespace std;
int n,m;
double ans;
struct A{
    int v,w;
    double p;
}a[105];
bool cmp(A &x,A &y){
    return x.p>y.p;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&a[i].v,&a[i].w);
        a[i].p=1.0*a[i].v/a[i].w;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        if(a[i].w<=m){
            ans+=a[i].v;
            m-=a[i].w;
        }
        else{
            ans+=m*a[i].p;
            break;
        }
    }
    printf("%.2lf",ans);
    return 0;
}