昨晚肝这一场是真的赔了,傻不拉几的C低级失误wa了一发,出完发现大家都会F然后跑去看了20min没头绪,折回去搞这个D,到最后也没过。。。感觉复杂度没错却一直tle,一直弄到两点受不了了睡觉去了,今早上课困得一批。
下午睡醒之后一直tle on test 27,给跪了好吧,疯狂卡常数真的有意思?最后把multiset改成priority_queue过了,真的服了,到目前为止52组数据吧,最狠的一组达到了2979ms,差21ms超时呵呵呵呵呵呵。。。
![](http://1.15.129.93/wp-content/uploads/2019/03/TIM图片20190306164809-300x70.png)
思路:首先找这个最小的数值肯定是二分,关键在于怎么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; }