题目翻译: Berland SU 今天为其学生举办了另一场培训比赛。n个 学生来了，每个人都带来了他的笔记本电脑。然而，事实证明，每个人都忘记带充电器了！

让学生编号从1 自n .笔记本电脑的我 -第个学生负责一个我 在比赛开始时，它使用b我 每分钟的电费（即，如果笔记本电脑有c 在某分钟开始时充电，它变成丙−b我 在下一分钟开始时充电）。整场比赛持续k 纪要。

Polycarp（Berland SU 的教练）决定购买一个充电器，以便所有学生都能顺利完成比赛。他在比赛开始的同时购买了充电器。

Polycarp 可以选择购买具有任何非负（零或正）整数功率输出的充电器。功率输出是在购买前选择的，购买后不能更改。让所选功率输出x .在每一分钟开始时（从比赛开始到比赛的最后一分钟），他可以将充电器插入学生的任何笔记本电脑，并使用它一定的整数分钟数。如果笔记本电脑正在使用b我 每分钟收费，然后它将变成b我−x 插入充电器时每分钟。负功耗率意味着笔记本电脑的电量正在增加。任何笔记本电脑的电量都不受限制，它可以变得无限大。充电器可以同时插入不超过一台笔记本电脑。

如果学生的笔记本电脑电量在某分钟开始时从未低于零，则学生成功完成了比赛（从比赛开始的分钟到比赛的最后一分钟，允许零充电）。比赛结束那一刻笔记本电脑的电量并不重要。

帮助 Polycarp 确定充电器应具有的最小可能功率输出，以便所有学生都能成功完成比赛。如果不存在此类充电器，还要报告。

输入 第一行包含两个整数n 和k (1≤n≤2⋅105 ,1≤k≤2⋅105 ） — 学生人数（以及相应的笔记本电脑）和比赛持续时间（以分钟为单位）。

第二行包含n 整数一个1,一个2，...，一个n (1≤一个我≤1012 ） — 每个学生笔记本电脑的初始费用。

第三行包含n 整数b1,b2，...，bn (1≤b我≤107 ） — 每个学生笔记本电脑的功耗。

输出 打印一个非负整数——充电器应具有的最小可能功率输出，以便所有学生都能成功完成比赛。

如果不存在此类充电器，请打印 -1。

例子

输入 2 4 3 2 4 2 输出 5

输入 1 5 4 2 输出 1

输入 1 6 4 2 输出 2

输入 2 2 2 10 3 15 输出 -1

注意 让我们来看看笔记本电脑在第一个带有电源充电器的示例中每分钟开始时的状态5 :

负责：[3,2] ，将充电器插入笔记本电脑 1; 负责：[3−4+5,2−2]=[4,0] ，将充电器插入笔记本电脑 2; 负责：[4−4,0−2+5]=[0,3] ，将充电器插入笔记本电脑 1; 负责：[0−4+5,3−2]=[1,1] . 比赛在第四分钟后结束。

但是，让我们考虑一下电源的充电器4 :

负责：[3,2] ，将充电器插入笔记本电脑 1; 负责：[3−4+4,2−2]=[3,0] ，将充电器插入笔记本电脑 2; 负责：[3−4,0−2+4]=[−1,2] ，第一台笔记本电脑带负电荷，因此，第一个学生没有完成比赛。 在第四个例子中，无论充电器多么强大，其中一名学生都无法完成比赛。

首先看题目是求最值,求最值,可以二分,贪心,优先队列,动态规划等.

这道题是求最少的充电功率,如果充电功率过低,都不能满足条件,充电功率到达某个值后都可以满足条件,符合二分的条件

然后看如何判断某个充电功率能否满足题目要求:这时就要贪心策略,来判断当前应该充哪台电脑

首先应该冲能当前能支撑时间最少的,因为其他的电脑还可以拖几分钟,这台电脑到那天没充就完了.如果能支撑到同样的天,应该先充消耗电多的,因为他最有可能在下分钟或者下下分钟再次没电.最后,如果前面都相同,那么应该优先充初始电量低的,因为其他都一样,没得比了

这个优先顺序是动态更新的,因为每次充电后都会变,所以要用优先队列动态更新

PS:对于临界条件第k天的判断要好好想一想,自己举个小例子.注意第k-1天消耗一次need后(从第0分钟开始,如同计时器从第0秒开始,到第k-1分钟,共消耗(k-1-0+1)次need)还有电就符合要求

思路&AC代码:

#include<queue>
#include<iostream>
#define inf 2000000000000 //2e5*1e7,极限情况这台电脑init=1,每天耗1e7,耗2e5天,其他电脑都符合要求
using namespace std;
using ll =long long;
int n,k;
struct node
{
    ll init,need,time;
  //优先队列中的结构体类型重载<运算符,像我这样写,满足返回true的条件的排后面
    bool operator < (const node &other) const
    {
        if(time!=other.time) {return time>other.time;}//time大的排后面
        else if(need!=other.need) {return need<other.need;}//需求小的排后面
        else {return init>other.init;}//初始电量多的排后面
    }
}lap[200010];
inline bool judge(ll power)
{
    priority_queue<node> pri;//因为每次处理时都充了电,所以队列是乱的,要重新加一个队列
    for(int i=1;i<=n;++i)
    {
        if(lap[i].init<lap[i].need*k)//支撑不到k天,消耗不了k次need,才加入队列,否则不用充电,别管
        {
            pri.push(node{lap[i].init, lap[i].need, lap[i].init/lap[i].need});
        }
    }
    if(pri.empty()) {return true;}//全都不用充电,直接符合要求
    for(int i=0;i<k;++i)//从第0天,到第k-1天耗电
    {
        node tmp=pri.top();
        pri.pop();
        if(tmp.time<i) {return false;}//电量只能消耗到i的前一天,没电了,不符合要求
     //下面判断是建立在time>=i的基础上
        else if((tmp.init+power)<tmp.need*k)//充了这次电,还不行,之后还要冲
        {
            tmp.init+=power;//记录充了这次电
            tmp.time=tmp.init/tmp.need;//判断充完电后又能撑到第几天
            pri.push(tmp);//又放回队列
        }
        if(pri.empty()) {return true;}//全部都>=tmp.need*k,能撑过这么多天,符合要求
    }
    return true;//队列中没有tmp.time<k-1的,也代表着能撑过这么多天,符合要求
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;++i) {cin>>lap[i].init;}
    for(int i=1;i<=n;++i) {cin>>lap[i].need;}
    ll l=0,r=inf,mid;
  //二分,相当于找>=的第一个
    while(l<r)
    {
        mid=(l+r)>>1;
        if(judge(mid)) {r=mid;}
        else {l=mid+1;}
    }
    if(l<inf) {cout<<l;}
    else {cout<<"-1";}//任意充电功率都不行,judge(mid)永远不满足,所以l一直=mid+1,知道while退出条件l>=r ==inf,
    return 0;
}

PS:在网上还看到一种时间复杂度为n的做法,也是先算出某台电脑最晚在几分钟要充电,然后从第0分钟到第n-1分钟累加充电次数,如果该次数>i,说明有需要两个充电器的时候,不符合要求,大家可以自行想想.

其实是我累了