2019 google kickstart round D food stalls

思路：

使用堆计算。参考了https://zhuanlan.zhihu.com/p/78702574。

实现：

 1 #include 
 2 using namespace std;
 3 typedef long long ll;
 4 const ll INF=0x3f3f3f3f3f3f3f3f;
 5 ll work(int lc,int rc,vector&c,vector&x){
 6     int n=c.size();
 7     vectorpre(n,INF),suf(n,INF);
 8     priority_queueq;
 9     ll sum=0;
10     for(int i=0;i){
11         ll val=c[i]-x[i];
12         if(lc==0){
13             pre[i]=0;
14             continue;
15         }
16         if(q.size()<lc){
17             q.push(val);
18             sum+=val;
19         }
20         else if(val<q.top()){
21             q.push(val);
22             sum+=val;
23             sum-=q.top();
24             q.pop();
25         }
26         if(q.size()==lc){
27             pre[i]=sum;
28         }
29     }
30     while(!q.empty())q.pop();
31     sum=0;
32     for(int i=n-1;i>=0;i--){
33         ll val=c[i]+x[i];
34         if(rc==0){
35             suf[i]=0;
36             continue;
37         }
38         if(q.size()<rc){
39             q.push(val);
40             sum+=val;
41         }
42         else if(val<q.top()){
43             q.push(val);
44             sum+=val;
45             sum-=q.top();
46             q.pop();
47         }
48         if(q.size()==rc){
49             suf[i]=sum;
50         }
51     }
52     ll res=INF;
53     int begin=lc==0?0:1;
54     int end=rc==0?n:n-1;
55     for(int i=begin;i){
56         ll l=0,r=0;
57         ll tmp=c[i];
58         if(lc>0){
59             l=pre[i-1]+x[i]*lc;
60         }
61         if(rc>0){
62             r=suf[i+1]-x[i]*rc;
63         }
64         res=min(res,tmp+l+r);
65     }
66     return res;
67 }
68 int main(){
69     ios::sync_with_stdio(false);
70     int T;cin>>T;
71     for(int t=1;t<=T;t++){
72         int k,n;cin>>k>>n;
73         vector>v;
74         vectorx(n),c(n);
75         for(int i=0;i){
76             cin>>x[i];
77         }
78         for(int i=0;i){
79             cin>>c[i];
80         }
81         for(int i=0;i){
82             v.push_back({x[i],c[i]});
83         }
84         sort(v.begin(),v.end());
85         for(int i=0;i){
86             x[i]=v[i].first;c[i]=v[i].second;
87         }
88 
89         ll res=work(k/2,k-k/2,c,x);
90 
91         cout<<"Case #"<": "<endl;
92     }
93     return 0;
94 }