K. Farm Management 【CCPC2024哈尔滨站】

K. Farm Management

思路:

很容易想到的策略：

1. 给每个作物都安排最短的时长$l$，剩下的时间作为可支配时间。
2. 选择删除收益最高的作物，然后将尽可能多的可支配时间用于这个作物。
3. 或者选择删除收益低时间还长的作物，然后将时间解放出来给收益更高的作物。

关键在于3，发现难以判断选择哪个作物，所以可以将2、3合为一起。即选择每一种作物，然后将可支配时间按照收益从高到低分配。由于选择的这个作物没有了时间限制，所以先将该作物的时间$l$解放出来加入到可支配时间中，然后按照$w$降序分配时间，而当分配到这个被选择的作物时，就应该用完剩余可支配时间，因为在它后面的作物收益都不如它。

实现细节: 按照w降序排列作物，保存 $(r-l)$ 和 $w(r-l)$ 的前缀和pc和pcw，然后遍历每种作物 i。如果可支配时间lt小于pc[i]时，可以二分pc找到能够分配到哪种作物。

代码:

#include <bits/stdc++.h>
#define endl '\n'
#define int long long 
#define pb push_back
#define pii pair<int,int>
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
using namespace std;
const int N = 100005;
struct zw{
int l,r,w,c,cw;
bool operator > (const zw &ohters)const {
return w > ohters.w;
}
}a[N];
int pc[N],pcw[N];  //r-l的前缀和 与  w(r-l)的前缀和

void solve() {
int n,t;
cin>>n>>t;
int sumt=0,lt,lans=0;
for(int i=1;i<=n;i++){
cin>>a[i].w>>a[i].l>>a[i].r;
a[i].c=a[i].r-a[i].l;
a[i].cw=a[i].c*a[i].w;
sumt+=a[i].l;
lans += a[i].l*a[i].w;
}
sort(a+1,a+n+1,greater<zw>()); //按照w降序排列作物
for(int i=1;i<=n;i++){
pc[i]=pc[i-1]+a[i].c;
pcw[i]=pcw[i-1]+a[i].cw;
}
int ans = 0;
for(int i=1;i<=n;i++){ //依次删除每种作物
int temp=lans-a[i].w*a[i].l; //temp是除当前删除作物外，其他作物都工作l时的收入和
lt =t-sumt+ a[i].l;  //lt是可支配的时间，尽可能多的把时间用在收益高的作物上
if(pc[i-1]<=lt){   //利用前缀和
temp+=pcw[i-1];
lt-=pc[i-1];
temp+= lt * a[i].w;  //i前面的作物时间都达到r时，剩余时间全部给i
}else{
int j = lower_bound(pc,pc+i,lt)-pc; //二分查找 可以分配到第j种作物
temp+=pcw[j-1]+a[j].w*(lt-pc[j-1]); 
}
ans = max(ans,temp);
}
cout<<ans<<endl;

}

signed main() {
cin.tie(0)->ios::sync_with_stdio(0);
int T = 1;
while (T--) {
solve();
}
return 0;
}

原文地址：https://blog.csdn.net/2303_79310336/article/details/143577844

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！