CF 3B. Lorry 点击打开链接
题意:有体积为1或2的物品共n种 你的容量为m,求你最多可以拿到多少价值的物品。
思路:贪心的思维 再加上尺取法求得最大的价值,这是我看大佬的博客才写出来的,故将之分类为转载。
定义一个结构体,记录体积 w,价值v,下标 index.然后将重量为1的按升序排在前面,重量为2的按降序排在后面,然后尺取。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> using namespace std; #define MAXN 100000+10 struct Node{ int w,v,index; }node[MAXN]; int n,m; int cmp(const Node &p,const Node &q){ if(p.w!=q.w){ return p.w<q.w; }else if(p.w==1){ return p.v<q.v; }else return p.v>q.v; } int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=1;i<=n;i++){ int x,y; scanf("%d%d",&x,&y); node[i].index=i; node[i].v=y; x==1?node[i].w=1:node[i].w=2; } sort(node+1,node+n+1,cmp); int MAX=0,w1=0,v1=0,MAXi=1; for(int i=1,j=1;i<=n;i++){ w1+=node[i].w; v1+=node[i].v; while(w1>m){ w1-=node[j].w; v1-=node[j].v; j++;//如果超过容量 就将上次加进来的减去,// } if(v1>MAX){MAX=v1;MAXi=j;}//用Max几录最大总价值// } printf("%d ",MAX); w1=v1=0; for(int j=MAXi;j<=n;j++){ w1+=node[j].w; v1+=node[j].v; if(w1>m)break; j==MAXi?printf("%d",node[j].index):printf(" %d",node[j].index); } puts(""); } return 0; }