[CF][二分check][贪心][×] codeforces 1132D Stressful Training

昨晚肝这一场是真的赔了，傻不拉几的C低级失误wa了一发，出完发现大家都会F然后跑去看了20min没头绪，折回去搞这个D，到最后也没过。。。感觉复杂度没错却一直tle，一直弄到两点受不了了睡觉去了，今早上课困得一批。

下午睡醒之后一直tle on test 27，给跪了好吧，疯狂卡常数真的有意思？最后把multiset改成priority_queue过了，真的服了，到目前为止52组数据吧，最狠的一组达到了2979ms，差21ms超时呵呵呵呵呵呵。。。

思路：首先找这个最小的数值肯定是二分，关键在于怎么check。然后这时候就请出在cf的cd题上经常出现的multiset同学了（雾其实最后我改用了优先队列才ac）：贪心的去check，要想保证这个charger尽可能地得到最好的利用，就在每一分钟都用上他，而对着谁用呢？当然是给最需要的电脑用了！最需要这个怎么量化？很简单维护每台电脑的gg掉的时间点，在multiset里按照这个时间从小到大排序就好了。

具体的实现的话，multiset里存的node需要存储的有

① 上次更改之后的总电量a
② 每分钟掉电量b
③ 上次更改的时间点post
④ 这个节点当前的要gg掉的时间点tm，浮点数
这样的话每次只要取出最小的tm的node，对他充电一分钟，再放回multiset就行了，如果取出来的这个早已gg过了，那就return false;如果一直到最后一分钟都可以这样进行下去就ok

优化：这个我感觉坑点就是常数优化，做了各种工作，比如以前我用的二分查找改成了l=-1,r=inf,while(r-l>1)这种貌似会快1个循环，还有就是用priority_queue代替multiset，因为这里只用到了第一个元素；再有就是用两个优先队列，一个用作原始备份，这样每次check只需要P=P1就可以了，不用自己手动重新把每个node塞进去。至于为什么这样会快一点我也不能具体的整出来，但是我相信写stl的人一定比我聪明^_^事实证明确实比我自己的快.

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e5 + 15;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxnode = 1e6 + 5;

typedef long long LL;
typedef unsigned long long ULL;


LL a[maxn];
int b[maxn];
struct node
{
    double tm;
    LL a,b,post;
    node(){a=b=post=0;tm=0.0;}
    node(LL a,LL b,LL post,double tm):a(a),b(b),post(post),tm(tm){}
    bool operator<(const struct node& rhs)const{
        return tm>rhs.tm;
    }
};


LL n,k;
LL pt,pa,pb,ptm,na;
double ntm;
node tn;
priority_queue<node> P1,P;

bool check(LL m)
{
    P=P1;
    for(int i=1;i<=k;i++)
    {
        tn=P.top();P.pop();
        pt=tn.post,pa=tn.a,pb=tn.b;ptm=tn.tm;
        if(ptm<i-1)
            return 0;
        na=pa-pb*(i-pt)+m;
        ntm=1.0*na/pb+i;
        P.emplace(na,pb,i,ntm);
    }
    return 1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
        P1.emplace(a[i],b[i],0,1.0*a[i]/b[i]);
    }
    LL l=-1,r=(LL)(2e12+5),m;
    while(r-l>1)
    { 
        m=(l+r)>>1;
        if(check(m))
            r=m;
        else
            l=m;
    }
    if(check(r)==0)
        cout<<-1;
    else
        cout<<r;
    return 0;
}