题目: CF1132D Stressful Training ,哈哈,我们今天来看一道稍微复杂一点的题嘛,这是选自codeforce上的一道题,好了,我们一起来看看题意吧:
考虑到直接复制题目,或者截屏的方式不是很方便阅读,我就把直接题目链接放下面!
题目传送门: CF1132D Stressful Training
思路
:
这道题思路就是采用贪心和二分的思想!!
我们先按照电脑能撑的时间时间从小到大排序,用一个优先队列来维护即可,我们每次判断队头是否符合条件即可,具体的直接看代码吧
我们来看看成功AC的代码吧:
#include<bits/stdc++.h> using namespace std; #define ll long long ll n,k; ll a[1000010],b[1000010]; ll l=0,r=2e12; struct node{ ll a,b; double c; bool operator < (const node &x)const { return c>x.c; } }; priority_queue<node> q; int check(ll x){ while(!q.empty()) q.pop(); for(int i=1;i<=n;i++){ if(a[i]*1.0/b[i]<k){ q.push({a[i],b[i],a[i]*1.0/b[i]}); } } if(q.empty()) return 1; //若队列为空,说明当前x 取大了,因为 所有电脑都能在k分钟内不关机 for(int i=0;i<k;i++){ node t = q.top(); q.pop(); t.a+=x; if(t.c<i) return 0;//这台电脑已经没电了 t.c=t.a*1.0/t.b; if(t.a*1.0/t.b<k){ q.push(t); } if(q.empty()) return 1; } return 1; } int main(){ cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i]; while(l<r){ ll mid=l+r>>1; if(check(mid)) r=mid; else l=mid+1; } if(l==2e12) cout<<-1<<"\n"; else cout<<l<<"\n"; return 0; }