首页 > 代码库 > Codeforces Beta Round #3 B. Lorry
Codeforces Beta Round #3 B. Lorry
一个贪心题写成这样也是醉了 ,这种状态注定要打酱油了么 ,不甘心啊~~
一辆车可以承载体积V的货物,A种物品1个单位体积,B种2个单位体积,某种物品虽然体积相同但是能力却不相同。
给出N个物品它的物品类型和能力值。求这辆车可以承载的物品的最大能力值之和是多少。
解题思路:
排序+贪心+条件判断,排序条件是单位体积的能力大小。
下面是代码:
#include <set> #include <map> #include <queue> #include <math.h> #include <vector> #include <string> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <cctype> #include <algorithm> #define eps 1e-10 #define pi acos(-1.0) #define inf 107374182 #define inf64 1152921504606846976 #define lc l,m,tr<<1 #define rc m + 1,r,tr<<1|1 #define zero(a) fabs(a)<eps #define iabs(x) ((x) > 0 ? (x) : -(x)) #define clear1(A, X, SIZE) memset(A, X, sizeof(A[0]) * (min(SIZE,sizeof(A)))) #define clearall(A, X) memset(A, X, sizeof(A)) #define memcopy1(A , X, SIZE) memcpy(A , X ,sizeof(X[0])*(SIZE)) #define memcopyall(A, X) memcpy(A , X ,sizeof(X)) #define max( x, y ) ( ((x) > (y)) ? (x) : (y) ) #define min( x, y ) ( ((x) < (y)) ? (x) : (y) ) using namespace std; struct node { int num,p; bool operator <(const node a )const { return a.p<p; } } num1[100005],num2[100005]; int main() { int n,v,t,cnt1=0,cnt2=0; scanf("%d%d",&n,&v); for(int i=0; i<n; i++) { scanf("%d",&t); if(t==1) { scanf("%d",&num1[cnt1].p); num1[cnt1++].num=i+1; } else { scanf("%d",&num2[cnt2].p); num2[cnt2++].num=i+1; } } sort(num1,num1+cnt1); sort(num2,num2+cnt2); int p1=0,p2=0,ans=0; while(v>1) { if(p1==cnt1) { if(p2==cnt2)break; else { v-=2; ans+=num2[p2].p; p2++; } } else if(p2==cnt2) { v--; ans+=num1[p1].p; p1++; } else { if(num1[p1].p*2>num2[p2].p) { v--; ans+=num1[p1].p; p1++; } else { v-=2; ans+=num2[p2].p; p2++; } } } if(v>1||v==0) { printf("%d\n",ans); for(int i=0; i<p1; i++) { printf("%d ",num1[i].num); } for(int i=0; i<p2; i++) { printf("%d ",num2[i].num); } } else if(v==1) { if(p1==cnt1) { if(p2==cnt2) { printf("%d\n",ans); for(int i=0; i<p1; i++) { printf("%d ",num1[i].num); } for(int i=0; i<p2; i++) { printf("%d ",num2[i].num); } } else { if(cnt1==0) { printf("%d\n",ans); for(int i=0; i<p1; i++) { printf("%d ",num1[i].num); } for(int i=0; i<p2; i++) { printf("%d ",num2[i].num); } } else { if(ans-num1[p1-1].p+num2[p2].p>ans) { printf("%d\n",ans-num1[p1-1].p+num2[p2].p); for(int i=0; i<p1-1; i++) { printf("%d ",num1[i].num); } for(int i=0; i<=p2; i++) { printf("%d ",num2[i].num); } } else { printf("%d\n",ans); for(int i=0; i<p1; i++) { printf("%d ",num1[i].num); } for(int i=0; i<p2; i++) { printf("%d ",num2[i].num); } } } } } else if(p2==cnt2) { printf("%d\n",ans+num1[p1].p); for(int i=0; i<=p1; i++) { printf("%d ",num1[i].num); } for(int i=0; i<p2; i++) { printf("%d ",num2[i].num); } } else { int ans1=ans-num1[p1-1].p+num2[p2].p; int ans2=ans+num1[p1].p; if(ans>=ans1&&ans>=ans2) { printf("%d\n",ans); for(int i=0; i<p1; i++) { printf("%d ",num1[i].num); } for(int i=0; i<p2; i++) { printf("%d ",num2[i].num); } } else if(ans1>=ans&&ans1>=ans2) { printf("%d\n",ans1); for(int i=0; i<p1-1; i++) { printf("%d ",num1[i].num); } for(int i=0; i<=p2; i++) { printf("%d ",num2[i].num); } } else if(ans2>=ans&&ans2>=ans1) { printf("%d\n",ans2); for(int i=0; i<=p1; i++) { printf("%d ",num1[i].num); } for(int i=0; i<p2; i++) { printf("%d ",num2[i].num); } } } } return 0; }
Codeforces Beta Round #3 B. Lorry
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。