自动搬运

查看原文

来自洛谷，原作者为

	longlinyu7 欲买桂花同载酒，终不似，少年游

搬运于2025-08-24 22:54:39，当前版本为作者最后更新于2024-01-22 19:20:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解决方法

电压越大，所得的总功率也就越大，而电压越小，所得的总功率也就略小，即电压与总功率满足单调性，可以考虑二分查找，写一个判断函数即可。

• 当总功率大于等于 $p$ 时，缩小右端点。

• 当总功率小于 $p$ 时，就扩大左端点。

判断函数中，注意对每一个机器的 $z$ 值进行讨论。判断函数时间复杂度为 $O(n)$。

最后，注意 $p$ 的范围，不要开小了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=105;
struct node{
    long long z,a,b;
}mp[N];
int n;
long long p;
bool judge(long long x){//二分查找
    long long sum=0;
    for(int i=1;i<=n;i++){
        if(x<=mp[i].z){
            sum+=mp[i].a*x;
        }
        else sum+=(mp[i].a*mp[i].z+mp[i].b*(x-mp[i].z));
    }
    return sum>=p;//比较
}
int main(){
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        cin>>mp[i].z>>mp[i].a>>mp[i].b;
    }
    long long l=1,r=p,mid,ans=0; //开 long long
    while(l<=r){
        mid=(l+r)>>1;
        if(judge(mid)){
            r=mid-1;
            ans=mid;
        }
        else {
            l=mid+1;
        }
    }
    cout<<ans;
    return 0;
}