• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 74,  comments - 33,  trackbacks - 0
            Sliding Window
            Time Limit: 12000MS Memory Limit: 65536K
            Total Submissions: 7213 Accepted: 1859
            Case Time Limit: 5000MS

            Description

            An array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
            The array is [1?3?-1?-3?5?3?6?7], and k is 3.
            Window positionMinimum valueMaximum value
            [1??3??-1]?-3??5??3??6??7?-13
            ?1?[3??-1??-3]?5??3??6??7?-33
            ?1??3?[-1??-3??5]?3??6??7?-35
            ?1??3??-1?[-3??5??3]?6??7?-35
            ?1??3??-1??-3?[5??3??6]?7?36
            ?1??3??-1??-3??5?[3??6??7]37

            Your task is to determine the maximum and minimum values in the sliding window at each position.

            Input

            The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.

            Output

            There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.

            Sample Input

            8 3
            1 3 -1 -3 5 3 6 7
            

            Sample Output

            -1 -3 -3 -3 3 3
            3 3 5 5 6 7
            

            Source

            POJ Monthly--2006.04.28, Ikki
            這題讓我想到了 幾個月前的浙大月賽題的區間最大最小值,用隊列維護的方法還是不會
            用線段樹AC,有點郁悶,我的半吊子線段樹啊?? 居然10s才ac,不過幸好服務器沒掛。。。。。。
            代碼如下
            ?
            #include<stdio.h>
            #include
            <string.h>
            #define?MAX?1001010
            struct?node{
            ????
            int?l,r;
            ????
            int?m;
            }
            ;
            node?Max_Stree[
            2*MAX];
            node?Min_Stree[
            2*MAX];
            int?w[MAX];
            int?getmax(int?a,int?b)
            {
            ????
            return?a>b?a:b;????
            }

            int?getmin(int?a,int?b)
            {
            ????
            return?a>b?b:a;????
            }

            int?Build_Max(int?now,int?l,int?r){
            ????Max_Stree[now].l
            =l;
            ????Max_Stree[now].r
            =r;
            ????
            if(l==r)Max_Stree[now].m=w[l];
            ????
            else?{
            ????????
            int?mid=(l+r)>>1;
            ????????
            int?max1=Build_Max(2*now,l,mid);
            ????????
            int?max2=Build_Max(2*now+1,mid+1,r);
            ????????Max_Stree[now].m
            =getmax(max1,max2);????
            ????}

            ????
            return?Max_Stree[now].m;????
            }

            int?Build_Min(int?now,int?l,int?r){
            ????Min_Stree[now].l
            =l;
            ????Min_Stree[now].r
            =r;
            ????
            if(l==r)Min_Stree[now].m=w[l];
            ????
            else?{
            ????????
            int?mid=(l+r)>>1;
            ????????
            int?min1=Build_Min(2*now,l,mid);
            ????????
            int?min2=Build_Min(2*now+1,mid+1,r);
            ????????Min_Stree[now].m
            =getmin(min1,min2);????
            ????}

            ????
            return?Min_Stree[now].m;????
            }

            int?Find_Max(int?now,int?l,int?r){
            ????
            int?left=Max_Stree[now].l;
            ????
            int?right=Max_Stree[now].r;
            ????
            if(left==l&&right==r)
            ????????
            return?Max_Stree[now].m;
            ????
            int?mid=(left+right)>>1;
            ????
            if(mid+1>r)return?Find_Max(2*now,l,r);
            ????
            if(mid<l)return?Find_Max(2*now+1,l,r);????
            ????
            else?return?getmax(Find_Max(2*now,l,mid),Find_Max(2*now+1,mid+1,r));
            }

            int?Find_Min(int?now,int?l,int?r){
            ????
            int?left=Min_Stree[now].l;
            ????
            int?right=Min_Stree[now].r;
            ????
            if(left==l&&right==r)
            ????????
            return?Min_Stree[now].m;
            ????
            int?mid=(left+right)>>1;
            ????
            if(mid+1>r)return?Find_Min(2*now,l,r);
            ????
            if(mid<l)return?Find_Min(2*now+1,l,r);????
            ????
            else?return?getmin(Find_Min(2*now,l,mid),Find_Min(2*now+1,mid+1,r));
            }
            posted on 2009-02-19 11:16 KNIGHT 閱讀(334) 評論(0)  編輯 收藏 引用
            <2009年2月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            1234567

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久久久久久亚洲Av无码| 亚洲精品乱码久久久久久久久久久久| 一本一本久久a久久精品综合麻豆| 99999久久久久久亚洲| 久久婷婷五月综合97色| 亚洲中文久久精品无码| 久久香综合精品久久伊人| 伊人久久大香线蕉精品不卡| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区 | 国产精品日韩欧美久久综合| 久久香蕉国产线看观看猫咪?v| 亚洲精品无码久久千人斩| 国产精品狼人久久久久影院| 国内高清久久久久久| 久久精品国产亚洲7777| 人妻精品久久无码专区精东影业| 婷婷综合久久狠狠色99h| 国产精品中文久久久久久久| 一本一道久久精品综合| 一本色道久久综合亚洲精品| 久久久无码精品午夜| 久久亚洲欧美日本精品| 欧美va久久久噜噜噜久久| 午夜精品久久久久久影视riav| 99久久99久久精品国产| 久久久久亚洲精品天堂| 亚洲AV日韩AV天堂久久| 国产精品久久久久久久久软件 | 久久综合鬼色88久久精品综合自在自线噜噜 | 久久人人爽人人人人爽AV| 久久久久久A亚洲欧洲AV冫| 国内精品久久久久| 久久99精品国产麻豆| 亚洲成色WWW久久网站| 性做久久久久久免费观看| 色欲综合久久躁天天躁| 久久无码一区二区三区少妇| 亚洲精品无码久久久| 亚洲精品国产综合久久一线| 欧美麻豆久久久久久中文| 伊人久久大香线蕉成人|