又一最大子段和（牛客小白月賽38 ）

題意：

我們將一個數(shù)列{an}的最大字段和的值記為S(a),現(xiàn)在你可以對進(jìn)行若干次操作，每次操作，你可以選擇數(shù)列中的一個數(shù)字，將其改為$[?10^{100},10^{100}]$之間的任意一個數(shù)。現(xiàn)在，給定整數(shù)x，求最少操作多少次可以使得S(a)=x
最大子段和是指選出數(shù)列中連續(xù)且非空的一段使得這段的和最大。

題解：

若S(a)=x,操作次數(shù)就是0
若S(a)<x，操作次數(shù)就是1，因為我們可以讓最大子段和中的某一個元素加上(x-s(a))
若S(a)>x是最難想的，我們先想另一個問題：最少改多少個元素可以讓S(a)<x?如果按照貪心的做法，當(dāng)算上當(dāng)前位第i位之后>x時，我們就要把第i位給改成負(fù)無窮($?10^{100}$)，這樣就可以使得S(a)一定小于x，這樣的操作次數(shù)記為ans1，現(xiàn)在每段都是小于x的，就變成了第二個情況，我們再操作一次就可以等于x，拿答案就是ans1+1。但實際上，這個1是可以省略的。
我們通過ans1次操作，將ans1個數(shù)改成極小值，這樣相當(dāng)于隔開好幾份，每份$su{m}_i$都小于x，那我們可以將兩個相鄰的sum1和sum2合并起來，讓他們等于x，這可以通過k值來實現(xiàn)，我們讓k取x-(sum1+sum2),這樣sum1+k+sum2不就等于k了，其他ans1-1個位置依舊取負(fù)無窮

代碼：

#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N = 400010; int main() { int _;cin>>_;while(_--){int n,x;cin>>n>>x;vector<ll>dp(n+1,0);ll maxv=-1e18;int cnt=0;for(int i=1;i<=n;i++){int xx;cin>>xx;dp[i]=xx;if(dp[i-1]>0) dp[i]+=dp[i-1];maxv=max(maxv,dp[i]);if(dp[i]>x){dp[i]-=1e18;cnt++;}}if(maxv==x) cout<<0<<endl;else if(maxv>x) cout<<cnt<<endl;else cout<<1<<endl;} return 0;} /** * In every life we have some trouble * When you worry you make it double * Don't worry,be happy. **/

總結(jié)

以上是生活随笔為你收集整理的又一最大子段和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。