程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVALive 6609（Minimal Subarray Length）維護遞增序列|RMQ

UVALive 6609（Minimal Subarray Length）維護遞增序列|RMQ

編輯：C++入門知識

題意：給一個整數序列（可能有負數），求最短的連續序列使得序列之和大於等於整數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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//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<第二份代碼：


/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//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<>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=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<