题面
传送门 https://codeforces.com/contest/1132/problem/D
分析
二分答案, 考虑如何判定
可以用贪心的方法, 每次找最快没电的电脑, 在没电前 1 单位时间给它充电
正确性显然
实现上可以维护一个堆, 存储每个电脑电用完的时刻, 每次从堆顶取出最小的一个给它充电. 设二分值为 mid, 对于每个电脑记录它的充电次数 num[i], 则没电的时间就是 \(\lfloor \frac{a_i+num_i\times mid}{b_i} \rfloor+1\)
如果在维护堆的过程中发现当前时间已经超过某个电脑的没电时间, 则返回 false
代码
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<queue>
- #define maxn 200005
- using namespace std;
- struct node{
- long long dtim;
- int id;
- node(){
- }
- node(int i,long long t){
- id=i;
- dtim=t;
- }
- friend bool operator <(node p,node q){
- return p.dtim>q.dtim;
- }
- };
- int n,k;
- long long a[maxn],b[maxn];
- long long num[maxn];
- bool check(long long add){
- priority_queue<node>q;
- for(int i=1;i<=n;i++){
- q.push(node(i,a[i]/b[i]+1));
- num[i]=0;
- }
- for(int i=1;i<=k;i++){
- node now=q.top();
- q.pop();
- if(now.dtim<i) return 0;
- num[now.id]++;
- long long sum=a[now.id]+num[now.id]*add;
- q.push(node(now.id,sum/b[now.id]+1));
- }
- return 1;
- }
- int main(){
- scanf("%d %d",&n,&k);
- for(int i=1;i<=n;i++){
- scanf("%I64d",&a[i]);
- }
- for(int i=1;i<=n;i++){
- scanf("%I64d",&b[i]);
- }
- long long l=0,r=1e13,ans=-1,mid;
- while(l<=r){
- mid=(l+r)>>1;
- if(check(mid)){
- ans=mid;
- r=mid-1;
- }else l=mid+1;
- }
- printf("%I64d\n",ans);
- }
来源: http://www.bubuko.com/infodetail-2981311.html