题意:给一个整数序列(可能有负数),求最短的连续序列使得序列之和大于等于整数x;
解法:第一种是On的复杂度:
我们要的是sum[j]-sum[i]>=x,如果有两个决策j < j‘,而且sum[j] >= sum[j‘],那么j就是没用的。即维护一个sum[j]递增序列。然后每次可以二分查找,但是这里有个特点就是要得到最近的,可以同时维护一个left指针,left指针用于跟进更行答案的左边界,因为维护的单调栈不会再右移到left左边去了(因为如果left右边还可以更新的答案肯定没有当前的小了)。
第二种是RMQ的做法,比较好理解:枚举i,然后求sum[j]-sum[i]>=x最小的j,那么就二分查找j。总复杂度nlogn
第一份代码:
/****************************************************** * author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <vector> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <string.h> //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 const double pi=acos(-1.0); typedef long long LL; const int Max=500100; const int INF=1000000007; int n,x; LL num[Max]; LL que[Max]; LL sum[Max]; int increase[Max]; int main() { int t;cin>>t; while(t--) { scanf("%d%d",&n,&x); for(int i=1;i<=n;i++) { scanf("%lld",num+i); sum[i]=sum[i-1]+num[i]; } int right=1; increase[0]=1; int left=0; int ans=n+1; for(int i=2;i<=n;i++) { while(right>left&&sum[increase[right-1]]>=sum[i]) right--; increase[right++]=i; while(right>left+1&&sum[i]-sum[increase[left]]>=x) { ans=min(ans,i-increase[left]); left++; } } if(ans==n+1) cout<<"-1\n"; else cout<<ans<<‘\n‘; } }第二份代码:
/****************************************************** * author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <vector> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <string.h> //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 const double pi=acos(-1.0); typedef long long LL; const int Max=500100; const int INF=1000000007; int n,x; LL dp[Max][30]; int mm[Max]; //初始化RMQ, b数组下标从1开始,从0开始简单修改 void RMQ(int n,LL b[]) { mm[0] = -1; for(int i = 1; i <= n; i++) { mm[i] = ((i&(i-1)) == 0)?mm[i-1]+1:mm[i-1]; dp[i][0] = b[i]; } for(int j = 1; j <= mm[n]; j++) for(int i = 1; i + (1<<j) -1 <= n; i++) dp[i][j] = max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); } //查询最大值 LL query(int x,int y) { int k = mm[y-x+1]; return max(dp[x][k],dp[y-(1<<k)+1][k]); } LL num[Max]; LL sum[Max]; int main() { int t; cin>>t; while(t--) { scanf("%d%d",&n,&x); for(int i=1; i<=n; i++) scanf("%lld",num+i),sum[i]=sum[i-1]+num[i]; RMQ(n,sum); int ans=n+3; for(int i=0; i<n; i++) { int l=i+1,r=n; while(l<r) { int mid=(l+r)/2; if(query(i+1,mid)-sum[i]>=x) r=mid; else l=mid+1; } if(sum[r]-sum[i]>=x) ans=min(ans,r-i); if(sum[l]-sum[i]>=x) ans=min(ans,l-i); } if(ans==n+3) ans=-1; cout<<ans<<endl; } return 0; }
UVALive 6609(Minimal Subarray Length)维护递增序列|RMQ,布布扣,bubuko.com
UVALive 6609(Minimal Subarray Length)维护递增序列|RMQ
原文:http://blog.csdn.net/xiefubao/article/details/25737615