又一最大子段和

大家好，今天我们来聊聊最大子段和是怎么回事呢？最大子段和相信大家都很熟悉，但是最大子段和又是怎么回事呢？下面就让小编带大家一起了解吧。最大子段和，其实就是最大子段和了。大家可能会感到很惊讶，最大子段和怎么......

我们将一个数列 $\{a_n\}$ 的最大子段和的值记为 $S(a)$ ，现在你可以对进行若干次操作，每次操作，你可以选择数列中的一个数字，将其改为 $[-10^{100},10^{100}]$ 之间的任意一个数。现在，给定整数 $x$ ，求最少需要操作多少次可以使得 $S(a)=x$ 。

最大子段和是指选出数列中连续且非空的一段使得这段的和最大。

输入第一行是一个整数 $T(1\leq T \leq 10^4)$ ，测试用例数。

每个测试用例的第一行包括两个数 $n(3\leq n \leq 10^5),x(-10^9\leq x \leq 10^9)$ ，表示数组的长度和需要达到的 $x$ 。

每个测试用例的第二行输入n个数字 $a_i(-10^9\leq a_i \leq 10^9)$ ，数组的 $n$ 个元素。

输入保证对于所有测试用例，有 $\Sigma n \leq 10^6$ 。

#include<bits/stdc++.h> using namespace std; int main() { int i,n,m,x,ans,flag,T; long long sum; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); flag=ans=sum=0; for(i=1;i<=n;i++) { scanf("%d",&x); sum=x+max(sum,(long long)0); if(sum>m)sum=-1,ans++; else if(sum==m)flag=1; } if(!flag)ans=max(ans,1); printf("%d\n",ans); } return 0; }

详情