P10098

longlinyu7 · 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;
}