CF436E

题意

给你 nn 种物品，每个物品可以不选，选一个代价为 aia_i ，选两个代价为 bib_i ，问恰好选 mm 的最小代价是多少。

1≤n≤3×105,0≤ai,bi≤109,m≤2n1\le n\le 3\times10^5,0\le a_i,b_i\le 10^9,m\le 2n

题解

很 naive 的想法可以 O(nm)O(nm) 背包，显然会 TLE。

考虑每个物品要么不选，要么选一选二，情况很少，考虑可反悔贪心。每次我们增加一个物品，希望花费最小的代价。那么有如下四种选择：

  1. 物品 xx 从零到一：+ax+a_x
  2. 物品 xx 从一到二：+bx−ax+b_x-a_x
  3. 物品 xx 从一到零，物品 yy 从零到二：+by−ax+b_y-a_x
  4. 物品 xx 从二到一，物品 yy 从零到二：+by−bx+ax+b_y-b_x+a_x

考虑如何维护：

  1. 小顶堆 Q1Q_1 维护 axa_x ，xx 当前选了零个
  2. 小顶堆 Q2Q_2 维护 bx−axb_x-a_x ，xx 当前选了一个
  3. 涉及到 x,yx,y 两个物品，分开维护： 小顶堆 Q3Q_3 维护 byb_y ， yy 当前选了零个， 小顶堆 Q4Q_4 维护 −ax-a_x ， xx 当前选了一个
  4. byb_y 同上，小顶堆 Q5Q_5 维护 −bx+ax-b_x+a_x ， xx 当前选了两个

每次判断哪个方案最优，并更新堆中物品就好了。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
#define fi first 
#define se second
using namespace std;
template <typename T>
inline void red(T &x) {
    x=0;bool f=0;char ch=getchar();
    while(ch<'0'||ch>'9') {(ch=='-')&&(f=-f),ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(T)(ch^48),ch=getchar();
    if(f) x=-x;

}
const int N = 300010;
typedef long long ll;
typedef pair<ll,int> pli;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const pli INF = pli(inf,-1);
int a[N],b[N],n,m;
int ct[N];
/*
1. x 0->1   +a_x                q1
2. x 1->2   +b_x-a_x            q2
3. x 1->0 y 0->2  +b_y-a_x      q3+q4
4. x 2->1 y 0->2  +b_y-b_x+a_x  q3+q5

q1 min a     ct[x]==0
q2 min b-a   ct[x]==1
q3 min b     ct[x]==0
q4 min -a    ct[x]==1
q5 min -b+a  ct[x]==2
*/
namespace Qheap{
    priority_queue<pli,vector<pli>,greater<pli> > q1,q2,q3,q4,q5; 
    pli Q1() {
        while(!q1.empty() && ct[q1.top().se]!=0 ) q1.pop();
        return (q1.empty())?INF:q1.top();
    }
    pli Q2() {
        while(!q2.empty() && ct[q2.top().se]!=1 ) q2.pop();
        return (q2.empty())?INF:q2.top();
    }
    pli Q3() {
        while(!q3.empty() && ct[q3.top().se]!=0 ) q3.pop();
        return (q3.empty())?INF:q3.top();
    }
    pli Q4() {
        while(!q4.empty() && ct[q4.top().se]!=1 ) q4.pop();
        return (q4.empty())?INF:q4.top();
    }
    pli Q5() {
        while(!q5.empty() && ct[q5.top().se]!=2 ) q5.pop();
        return (q5.empty())?INF:q5.top();
    }
    void updata(int id) {
        if(ct[id]==0) {
            q1.push(pli(a[id],id));
            q3.push(pli(b[id],id));
        }
        if(ct[id]==1) {
            q2.push(pli(b[id]-a[id],id));
            q4.push(pli(-a[id],id));
        }
        if(ct[id]==2) {
            q5.push(pli(-b[id]+a[id],id));
        }
    }
}
using namespace Qheap;
int main() {
    red(n);red(m);
    for(int i=1;i<=n;++i) red(a[i]),red(b[i]),updata(i);
    ll ans=0;
    while(m--) {
        pli A=Q1(),B=Q2(),C=Q3(),D=Q4(),E=Q5(); ll MIN;
        MIN=min(min(A.fi,B.fi),min(C.fi+D.fi,C.fi+E.fi));
        if(A.fi==MIN) {
            ans+=A.fi; ct[A.se]++; updata(A.se);
        }else if(B.fi==MIN) {
            ans+=B.fi; ct[B.se]++; updata(B.se);
        }else if(C.fi+D.fi==MIN) {
            ans+=C.fi+D.fi; ct[C.se]+=2; updata(C.se); ct[D.se]--; updata(D.se); 
        }else {
            ans+=C.fi+E.fi; ct[C.se]+=2; updata(C.se); ct[E.se]--; updata(E.se); 
        }
    }
    printf("%lld\n",ans);
    return 0;
}