题解：P10051 [CCO2022] Rainy Markets

· · 题解

思维难度较大，感觉有个蓝题？
首先判断一个无解情况：u_i+b_i+b_{i+1}<p_i。很好理解，最优情况都无法满足，那就一定无法满足了。

鉴于要输出方案，我们最好开数组来记录。

先设 f_i 表示在第 i 个车站至多留下多少个人，显然可以推出递推式：

f_i = \max(0,b_i - \max(p_{i-1}-f_{i-1},0))

大概就是要除去在第 i-1 个车站实在没法挤的人数，并于 0 取最大值，即最坏也是不容纳人。

设 l_i,buy_i,r_i 分别为在第 i 个市场中呆着不懂，去买伞与到 i+1 车站的人数。

我们可以从右向左贪心（具体待会简单解释以下）。

显然，向右侧多分配人是更优的（毕竟右边已经尽量优的处理过了）。

分配完之后，因为要使得买伞的人的数量少，就尽量多的原地不动，这样就用上了 f_i，也说明了为什么要从右向左贪心。

实在不行的话，只能让剩余的人买伞了。

还是不行的话，就要让剩下的原地不动了（因为没法再分配了）。若剩下的人数大于了容量，便无解。

代码

#include<iostream>
using namespace std;
#define int long long 
const int N=1e6+10;
int n;
int b[N],p[N],u[N];
int f[N];
int l[N],r[N],buy[N];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld",&b[i]);
    }
    for(int i=1;i<n;i++){
        scanf("%lld",&p[i]);
    }
    for(int i=1;i<n;i++){
        scanf("%lld",&u[i]);
        if(u[i]+b[i]+b[i+1]<p[i]){
            cout<<"NO";
            return 0;
        }
    }
    for(int i=1;i<=n;i++){
        f[i]=max(0ll,b[i]-max(p[i-1]-f[i-1],0ll));
    }
    long long res=0;
    for(int i=n-1;i;i--){
        r[i]=min(p[i],b[i+1]-l[i+1]);
        p[i]-=r[i];
        l[i]=min(p[i],f[i]);
        p[i]-=l[i];
        buy[i]=min(p[i],u[i]);
        p[i]-=buy[i];
        l[i]+=p[i];
        res+=buy[i];
        if(l[i]>b[i]){
            cout<<"NO";
            return 0;
        }
    }
    printf("YES\n%lld\n",res);
    for(int i=1;i<n;i++){
        printf("%lld %lld %lld\n",l[i],buy[i],r[i]);
    }
}