1 条题解
-
0
注意到我们不能很好地直接固定光盘的数量,所以考虑 WQS 二分,给每个光盘增加一个负的贡献 。
而如何计算最大的贡献?考虑从前到后扫描一遍做反悔贪心。每次先把 加入堆中,并取出堆顶,若与 组成的光盘对结果的贡献是整数,就立刻添加该光盘,并把 加入堆中,这样后面可以让 更换匹配的 来产生更加优秀的解。
时间复杂度 。
/** * @date: 2024.01.29 * @problem: P4694 * @tags: WQS 二分, 贪心, 反悔贪心 */ #include<bits/stdc++.h> using namespace std; int n,k,a[500001],b[500001]; pair<long long,int> calc(int mid){ priority_queue<pair<long long,bool> > Q; long long answer=0; int total=0; for(int i=1;i<=n;i++){ Q.push({-a[i],true}); auto data=Q.top(); if(b[i]-data.first-mid<0){ answer+=b[i]-data.first-mid; if(data.second)total++; Q.pop(); Q.push({b[i]-mid,false}); } } return{answer,total}; } int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",a+i); for(int i=1;i<=n;i++) scanf("%d",b+i); int l=0,r=2e9; while(l<r){ int mid=(1ll*l+r+1)>>1; auto result=calc(mid); if(result.second<=k)l=mid; else r=mid-1; } printf("%lld\n",calc(l).first+1ll*l*k); return 0; }
- 1
信息
- ID
- 3624
- 时间
- 4000ms
- 内存
- 500MiB
- 难度
- 7
- 标签
- 递交数
- 3
- 已通过
- 2
- 上传者