codeforces 808E Selling Souvenirs

（ACM）二分

题意

• 01背包
• 物品体积只取1,2,3
• 物品个数1e5

题解

• 假设取的个数分别是c1,c2,c3，那么c1+2*c2+3*c3<=m
• 枚举c3，则c1+2*c2<=m-3*c3=k
• 现在要考虑的是c1和c2如何决定。
  
  • 情况一：c2=0,c1=min(k,sum1)
  • 情况二：c2=1，那么c1最小价值的两个就要被替换
  • 一直增加c2直到增加的物品价值比被替换的物品价值低
  • 这一部分可以用二分完成

代码

#include<map>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100005;
int n,m;
int a[4][N];
ll sum[4][N];
int main() {
    while(~scanf("%d%d",&n,&m)) {
        ///init
        memset(a,0,sizeof(a));
        memset(sum,0,sizeof(sum));
        ///read
        for(int i=1;i<=n;++i) {
            int w,c;scanf("%d%d",&w,&c);
            a[w][++a[w][0]]=-c;
        }
        ///sort
        for(int i=1;i<=3;++i) {
            sort(a[i]+1,a[i]+1+a[i][0]);
        }
        ///get sum
        for(int i=1;i<=3;++i) {
            for(int j=1;j<=a[i][0];++j) {
                sum[i][j]=sum[i][j-1]-a[i][j];
            }
        }
        ///solve
        ll ans=0;
        for(int c3=0;c3<=a[3][0];++c3) {//for w==3
            if(c3*3>m) break;
            int k=m-c3*3;
            ///bin
            int l=1,r=min(k/2,a[2][0]),c2=0;
            while(l<=r) {
                int mid=(l+r)>>1;
                int t=-a[2][mid];
                int prec2=mid-1;
                int prec1=k-prec2*2;
                if(1<=prec1&&prec1<=a[1][0]) t=t+a[1][prec1];
                if(1<=prec1-1&&prec1-1<=a[1][0]) t=t+a[1][prec1-1];
                if(t>0) {
                    c2=mid;
                    l=mid+1;
                } else {
                    r=mid-1;
                }
            }
            ///upd
            int c1=k-c2*2;
            if(c1>a[1][0]) c1=a[1][0];
            if(c2>a[2][0]) c2=a[2][0];
            ans=max(ans,sum[1][c1]+sum[2][c2]+sum[3][c3]);
        }
        ///print
        printf("%I64d\n",ans);
    }
    return 0;
}