CF1132D Stressful Training(binary search)(greedy)

    科技2022-07-10  133

    题意: 有n台电脑,每台电脑,他的初始电量为a[i],每分钟消耗电量为b[i]你有一个功率为的充电器,每分钟可以使一台电脑电量增加x。问,x至少为多大才能保证在[0,k)的时间内任意一台电脑电量都不为负 题解: 我们对于这个x进行二分操作。 那么这个check函数怎么写呢 首先我们想如果保证每天电脑都尽量都有电,那么我们肯定是对 最快没电的那台电脑进行充电(贪心策略),如何找出最快没有电的那台电脑,因为我们需要遍历完1-k 分钟,每次都要找到最快没有电的那台电脑,如何操作呢? 那肯定是优先队列了,我们对优先队列重载以下操作符,让他按照(当前电量/每分钟耗电量)从小到大进行排序。 充电时间均为整数,求最小的ans使得在k分钟内的每一分钟开始的时刻每一台电脑的电量都大于等于零。 注意:在check的时候 1.第i分钟开始的时候电量为负时,返回false 2.最早耗完电的电脑都比k大,直接放回true。

    /*Keep on going Never give up*/ //#pragma GCC optimize(3,"Ofast","inline") #include<bits/stdc++.h> #define int long long #define endl '\n' #define Accepted 0 #define AK main() #define I_can signed using namespace std; const int maxn =2e5+10; const int MaxN = 0x3f3f3f3f; const int MinN = 0xc0c0c00c; typedef long long ll; const int inf=0x3f3f3f3f; const ll mod=1e9+7; using namespace std; string s[maxn]; //struct rule{ // bool operator()(const string & s ) //}; int n,m; int a[maxn],b[maxn]; struct node{ int ans,cnt,rate; node(int x,int y){ans=x,cnt=y,rate=x/y;} bool operator <(const node & oth)const { return rate>oth.rate; } }; bool che(int x){ priority_queue<node> q; for(int i=1;i<=n;i++) q.push(node(a[i],b[i])); for(int i=1;i<=m;i++){ node temp=q.top(); q.pop(); if(temp.rate<i-1) return false; if(temp.rate>=m) return true; q.push(node(temp.ans+x,temp.cnt)); } return true; } I_can AK{ ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i]; int l=0,r=1e15; ll ans=-1; while(l<=r){ int mid=(l+r)/2; if(che(mid)){ ans=mid; r=mid-1; } else l=mid-1; } cout<<ans<<endl; return Accepted; }
    Processed: 0.068, SQL: 8