K. Farm Management
思路:
很容易想到的策略:
- 给每个作物都安排最短的时长 l l l,剩下的时间作为可支配时间。
- 选择删除收益最高的作物,然后将尽可能多的可支配时间用于这个作物。
- 或者选择删除收益低时间还长的作物,然后将时间解放出来给收益更高的作物。
关键在于3,发现难以判断选择哪个作物,所以可以将2、3合为一起。即选择每一种作物,然后将可支配时间按照收益从高到低分配。由于选择的这个作物没有了时间限制,所以先将该作物的时间 l l l解放出来加入到可支配时间中,然后按照 w w w降序分配时间,而当分配到这个被选择的作物时,就应该用完剩余可支配时间,因为在它后面的作物收益都不如它。
实现细节: 按照w降序排列作物,保存 ( r − l ) (r-l) (r−l) 和 w ( r − l ) 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;
}