Stressful Training(CF1132D)

Stressful Training

https://ac.nowcoder.com/acm/problem/113525

题意

个学生要打一场分钟的比赛。(n,k<=2e5)

每个学生的电脑有初始电量和每分钟耗电量(电量在这一分钟的最后一刻结算,即在下一分钟时才会减少,最终电量允许为负)。(ai<1e12,bi<1e7)

学生们买了一个充电器,功率为任意值,每分钟可以使电量增加。D

问题:求最小的,使所有学生的电脑的电量在分钟内都不为负。

思路

二分答案+贪心。每分钟都给当前续航时间最少的电脑充电,如果续航时间相同给耗电量大的电脑先充电,都相同则给剩余电量少的电脑先充电。那么可以按照此规则维护一个优先队列,每次给队首元素充电,如果其续航时间超过k则弹出队列。一共执行k次,若当前续航时间小于当前天数则失败,撑过k天或者队列为空则成功。优先队列的建堆复杂度,插入删除为,算法复杂度为

二分右边界开太大爆long long了一次。还要注意优先队列定义规则里面的大于号和小于号。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
ll al[maxn], be[maxn];
ll n,k;
const ll inf = 2e12;
struct node {
    ll d, a, b; // d=a/b
    node (ll dd, ll aa, ll bb) {
        d=dd; a=aa; b=bb;
    }
    bool operator < (const node &p) const { // 最后还有一个const
        if(d == p.d && b == p.b) return a>p.a;
        if(d == p.d) return b<p.b;
        return d > p.d;
    }
};

priority_queue<node> q;

bool check(ll mid) {
    priority_queue<node> qq=q;
    for(int i=0;i<k;i++) {
        if(qq.empty()) return 1;
        node p=qq.top();
        qq.pop();
//        cout << p.d << ' ' << p.a <<  " " << p.b << endl;
//        cout<<p.d <<"  " << i << endl;
        if(p.d < i) return 0;
        if((p.a+mid)/p.b < k) {
            qq.push(node((p.a+mid)/p.b, p.a+mid, p.b));
        }
    }
    return 1;
}

int main() {
    scanf("%lld%lld",&n,&k);
    for(int i=0;i<n;i++) scanf("%lld",&al[i]);
    for(int i=0;i<n;i++) scanf("%lld",&be[i]);
    for(int i=0;i<n;i++) {
        if(al[i]/be[i] < k)
            q.push(node(al[i]/be[i],al[i],be[i]));
    }
    ll l=0,r=inf,ans=inf,mid;
    while(l<=r) {
//        cout << "mid = " << mid << endl;
        mid = (l+r)>>1;
        if(check(mid)) ans = min(ans, mid), r=mid-1;
        else l=mid+1;
    }
    if(ans==inf) ans=-1;
    printf("%lld\n", ans);
}
全部评论

相关推荐

11-09 14:54
已编辑
华南农业大学 产品经理
大拿老师:这个简历,连手机号码和照片都没打码,那为什么关键要素求职职位就不写呢? 从上往下看,都没看出自己到底是产品经理的简历,还是电子硬件的简历? 这是一个大问题,当然,更大的问题是实习经历的描述是不对的 不要只是去写实习流程,陈平,怎么去开会?怎么去讨论? 面试问的是你的产品功能点,是怎么设计的?也就是要写项目的亮点,有什么功能?这个功能有什么难处?怎么去解决的? 实习流程大家都一样,没什么优势,也没有提问点,没有提问,你就不得分 另外,你要明确你投的是什么职位,如果投的是产品职位,你的项目经历写的全都是跟产品无关的,那你的简历就没用 你的面试官必然是一个资深的产品经理,他不会去问那些计算机类的编程项目 所以这种四不像的简历,在校招是大忌
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
10-05 10:13
已编辑
HHHHaos:让这些老登来现在秋招一下,简历都过不去
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务