欧美三区_成人在线免费观看视频_欧美极品少妇xxxxⅹ免费视频_a级毛片免费播放_鲁一鲁中文字幕久久_亚洲一级特黄

[ACM] POJ 3061 Subsequence (仿真足)

系統 1781 0

Subsequence
Time Limit: ?1000MS ? Memory Limit: ?65536K
Total Submissions: ?8403 ? Accepted: ?3264

Description

A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.

Input

The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.

Output

For each the case the program has to print the result on separate line of the output file.if no answer, print 0.

Sample Input

      2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5
    

Sample Output

      2
3
    

Source


題意為:給定長度為n的整數數列以及整數S,求出總和不小于S的連續子序列的長度的最小值。假設解 不存在,輸出0.

第一種方法:

先求出sum[i],從第1個數到第i個數的區間和,每次固定一個開始查找的起點sum[i], ?然后採用二分查找找到 sum[i] + S 的位置,區間長度即為(末位置-(起始位置-1)),用ans保存過程中區間的最小值。時間復雜度 0(nlogn)

代碼:

      #include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn=100010;
int num[maxn];
int sum[maxn];
int n,S;

int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&S);
        sum[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
            sum[i]=sum[i-1]+num[i];
        }
        if(sum[n]<S)
        {
            cout<<0<<endl;
            continue;
        }
        int ans=maxn;
        for(int s=0;sum[s]+S<=sum[n];s++)//從sum[s+1]開始查找,s是開始查找的數的前一個位置
        {
            int t=lower_bound(sum+s+1,sum+n+1,sum[s]+S)-(sum+s);//sum+s是從第sum+s+1個地址開始查找的前一個地址,所以找到的地址減去這個地址即為區間長度
            ans=min(ans,t);
        }
        printf("%d\n",ans);
    }
    return 0;
}
    

另外一種方法:尺取法

重復地推進區間的開頭和末尾 ,來求滿足條件的最小區間的方法稱為尺取法。

主要思想為:當a1, ?a2 ?, a3 滿足和>=S,得到一個區間長度3,那么去掉開頭a1, ? 剩下 a2,a3,推斷是否滿足>=S,假設滿足,那么區間長度更新,假設不滿足。那么尾部向后拓展,推斷a2,a3,a4是否滿足條件。

反復這種操作。

個人對尺取法的理解:

當一個區間滿足條件時。那么去掉區間開頭第一個數,得到新區間。推斷新區間是否滿足條件,假設不


滿足條件。那么區間末尾向后擴展,直到滿足條件為之。這樣就得到了很多滿足條件的區間,再依據題


意要求什么,就能夠在這些區間中進行選擇,比方區間最長,區間最短什么的。

這樣跑一遍下來。時間


復雜度為O(n)。

代碼:

      #include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int maxn=100010;
int num[maxn];
int n,S;

int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&S);
        for(int i=1;i<=n;i++)
            scanf("%d",&num[i]);
        int sum=0,s=1,e=1;
        int ans=n+1;
        for(;;)
        {
            while(e<=n&&sum<S)
                sum+=num[e++];
            if(sum<S)
                break;
            ans=min(ans,e-s);
            sum-=num[s++];
        }
        if(ans==n+1)
            cout<<0<<endl;
        else
            cout<<ans<<endl;
    }
    return 0;
}
    

另外一種方法求區間長度的方法為 (末位置+1-起始位置)




版權聲明:本文博客原創文章,博客,未經同意,不得轉載。

[ACM] POJ 3061 Subsequence (仿真足)


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦?。?!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 一级片视频免费 | 国产精品v在线播放观看 | 福利视频在线观看www. | 久久se精品一区二区国产 | 精品一区二区三区的国产在线观看 | 91视频苹果版 | 伊人久操| 欧美精品v国产精品v日韩精品 | 久久精品一区二区三区四区 | 国产一区| 久久久久久中文字幕 | 成人在线精品视频 | 亚洲国产综合精品 | 久久久久国产精品免费免费搜索 | 亚洲第一区精品观看 | 免费精品一区二区三区在线观看 | 亚洲视频在线播放 | 日韩成人免费电影 | 精品国产一区二区三区成人 | 久久大香香蕉国产免费网站 | 国产福利免费在线观看 | 2019中文字幕在线播放 | 99久久久国产精品免费观看 | 中文字幕在线免费视频 | 日本在线播放不卡一区二区三区 | 国产一区在线看 | 久久性 | 久久99精品视免费看 | 深夜网址你懂的 | 欧美1级| 日韩女同一区二区三区 | 久久经典视频 | 国产精品男人的天堂 | 国产成人啪精品视频免费网站软件 | 欧美精彩视频 | 国产毛片精品 | 欧美日韩亚洲高清不卡一区二区三区 | 精品久久一区二区三区 | 黄色激情小视频 | 自拍偷拍av | 比比资源先锋影音网 |