为什么呢?
查看原帖
为什么呢?
1026796
Xiaoxiaotian楼主2024/8/5 18:01

大家看下,下面是一个十分普通的通用贪心解法, 为什么只有30分呢(本人没学过01背包)?

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
struct t{
    int v,w;
}j[30];
bool cmp(t a,t b){
    if(a.v*a.w!=b.v*b.w)return a.v*a.w>b.v*b.w;
    return a.w>b.w;
    
}
int main(){
   cin>>n>>m;
   for(int i=1;i<=m;i++){
       cin>>j[i].v>>j[i].w;
   }
   sort(j+1,j+m+1,cmp);
   for(int i=1;i<=m;i++){
       if(j[i].v<=n){
           ans+=j[i].v*j[i].w;
           n-=j[i].v;
       }
       if(n==0)break;
   }
   cout<<ans;
   return 0;
}
2024/8/5 18:01
加载中...