算法也太难了吧


私信TA

用户名:17306366773

访问量:10833

签 名:

我口袋只剩玫瑰一片,此行又山高路远

等  级
排  名 427
经  验 4722
参赛次数 0
文章发表 41
年  龄 0
在职情况 学生
学  校 天津工业大学
专  业

  自我简介:

解题思路:
    贪心+单位价值排序
注意事项:
他装的是散货!

他装的是散货!

他装的是散货!

参考代码:

#include#includeusing namespace std;
struct huo{
    double g,p;
    double v;
}h[10005];
bool cmp(huo a,huo b){
    return a.v>b.v;
}
int main(){
    int w,n;
    cin>>n>>w;
    for(int i=0;i>h[i].g>>h[i].p;
        h[i].v=h[i].p/h[i].g;
    }
    sort(h,h+n,cmp);
    double weight=0,value=0;
    for(int i=0;i<n;i++){
        if(weight+h[i].g<=w){
            weight+=h[i].g;
            value+=h[i].p;
        }else {
            value+=h[i].v*(w-weight);
            break;
        }
    }
    printf("%.1lf\n",value);
}


 

0.0分

3 人评分

  评论区