自动搬运

查看原文

来自洛谷，原作者为

	tuntunQwQ 大枣莲子枸杞水

搬运于2025-08-24 23:15:32，当前版本为作者最后更新于2025-05-26 22:18:48，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

因为我们每次都只能取每行最左侧的元素，我们可以记录列表的前缀和数组 $sum$。

在一行中，当遍历到第 $i$ 列时满足 $sum_i>0$，就说明我们如果取走 $1$ 至 $i$ 列的元素，$x$ 的值会增加。但是我们要保证在任意时刻 $x$ 非负，就需要计算出 $sum_1,sum_2,...,sum_i$ 的最小值，如果最小值大于 $x$，我们就无法使 $x$ 非负。

我们不妨这样想，要想获得 $sum_i$ 的加分，必然要有 $sum_1,sum_2,...,sum_i$ 的最小值的花费，对于每组“加分”，记录它加分和花费的多少，每次优先选择花费少的进行加分。如果 $x$ 的值不小于当前最小的花费，我们就可以更新 $x$。

注意如果 $sum_{i-1}>0$，从 $sum_i$ 开始的前缀和应该从头开始计算，否则在计算本组加分的值时，上组加分的值也会被计算。

至于每行中每组加分是否是按照从左到右的顺序被选择，因为每行中靠右的组的花费一定不小于靠左的组的花费，所以不会影响答案。

代码如下，可供参考：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int x,k,l,a,sum[N],mi,cnt;
pair<int,int> p[N];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
    cin>>x>>k;
    for(int i=1;i<=k;i++){
        cin>>l;
        mi=2147483647;
        for(int j=1;j<=l;j++){
            cin>>a;
            sum[j]=sum[j-1]+a;
            if(sum[j]>0)p[++cnt]={-mi,sum[j]},sum[j]=0;
            else mi=min(mi,sum[j]);
        }
    }
    sort(p+1,p+cnt+1);
    for(int i=1;i<=cnt;i++){
    	int a=p[i].first,b=p[i].second;
    	if(x>=a)x+=b;
    	else break;
	}
    cout<<x;
    return 0;
}