首页 > 代码库 > cf808E(三分)
cf808E(三分)
题目链接：http://codeforces.com/problemset/problem/808/E
题意：给出n个体积为wi, 价值为ci的物品，背包容量为m，求能容纳的最大物品价值，其中 1<=wi<=3；
思路：看到题目首先想到了atcoder的一道题http://www.cnblogs.com/geloutingyu/p/6789985.html
然而这里的 n 为 1e5，直接贪心枚举肯定是不行的．可以考虑O(nlogn)的算法．．．
这里可以先按照价值从大到小枚举体积为3的物品，用剩余的容量去装体积为1, 和 2 的物品使剩余空间取得最大值，所有枚举情况中的最大值即为答案；
现在问题转化成了在O(longn)的时间复杂度内求出剩余空间能容纳的1，和２物品最大价值，以物品２的数目为 x 轴，能容纳的最大价值为 y 轴，
将其描点再连成光滑曲线后是一条单峰抛物线 / 单峰拋物线的一侧 ；可以做个简易的证明，对于已经降序排列的物品1, 物品2 显然其单位体积的
价值是非递增的，用 i 表示当前选了 i 个物品2，area2( i )为前 i 个物品平均单位体积的价值，显然 area2( i )是随 i 非递增的，物品１同理，并且这里的容量是固定的，
所以其在以物品２的数目为x轴，最大价值为 y 轴的直角坐标系中的图形为：
１，若物品1, 2的体积和不大于背包剩余空间，则其为单峰函数的左侧；
２，对于物品1, 2的体积和大于背包剩余空间，有：
a，若area2(index2) > area1(1)，其中index2为物品2的数目，则其为单峰函数左侧；
b，若area2(1) < area1(index1)，其中index1为物品1的数目，则其为单峰函数右侧；
c，其他情况则存在峰；
对于单峰函数直接三分一下物品２的数目即可找峰值，注意这里可能会存在单调的情况(为单峰函数的一侧)，所以还要判断一下边界；
ps：我试了下先枚举物品３再三分物品１的数目wa了，百思不得其解，望路过的大佬指教～
代码：
1 #include <iostream> 2 #include <stdio.h> 3 #include <algorithm> 4 #define ll long long 5 using namespace std; 6 7 const int MAXN = 3e5+10; 8 ll a[MAXN], b[MAXN], c[MAXN]; 9 ll va[MAXN], vb[MAXN], vc[MAXN]; 10 int n, m, indxa=1, indxb=1, indxc=1; 11 12 bool cmp(ll a, ll b){ 13 return a > b; 14 } 15 16 void get_v(void){ 17 for(int i=1; i<=m; i++){ 18 va[i] = va[i-1] + a[i]; 19 } 20 for(int i=1; i*2<=m; i++){ 21 vb[i<<1] = vb[(i-1)<<1] + b[i]; 22 vb[(i<<1)-1] = vb[(i-1)<<1]; 23 } 24 for(int i=1; i*3<=m; i++){ 25 vc[i*3] = vc[(i-1)*3] + c[i]; 26 } 27 } 28 29 ll f(int x, int w){ 30 if(x*2 > w) x=w>>1; 31 return vb[x*2] + va[w-x*2]; 32 } 33 34 ll find(int w){//三分体积为2的数目 35 if(w <= 0) return 0; 36 int l=0, r=w, rmid=w, lmid=0; 37 while(l < r-2){ 38 lmid = l+(r-l)/3; 39 rmid = r-(r-l)/3; 40 if(f(lmid, w) > f(rmid, w)) r = rmid; 41 else l = lmid; 42 } 43 return max(max(max(max(f(l, w), f(r, w)), f(lmid, w)), f(rmid, w)), f(0, w));//***注意这里的边界条件 44 } 45 46 int main(void){ 47 ll ans=0; 48 scanf("%d%d", &n, &m); 49 for(int i=0; i<n; i++){ 50 int x, y; 51 scanf("%d%d", &x, &y); 52 if(x == 1) a[indxa++] = y; 53 else if(x == 2) b[indxb++] = y; 54 else c[indxc++] = y; 55 } 56 sort(a+1, a+indxa, cmp); 57 sort(b+1, b+indxb, cmp); 58 sort(c+1, c+indxc, cmp); 59 get_v(); 60 for(int i=0; i*3<=m; i++){//枚举体积为3的数目 61 ll cnt = vc[i*3]; 62 cnt += find(m-i*3); 63 ans = ans > cnt ? ans : cnt; 64 } 65 printf("%lld\n", ans); 66 return 0; 67 }
cf808E(三分)