• <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
            這題讓我想到了 幾個(gè)月前的浙大月賽題的區(qū)間最大最小值,用隊(duì)列維護(hù)的方法還是不會(huì)
            用線段樹AC,有點(diǎn)郁悶,我的半吊子線段樹啊?? 居然10s才ac,不過(guò)幸好服務(wù)器沒(méi)掛。。。。。。
            代碼如下
            ?
            #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) 評(píng)論(0)  編輯 收藏 引用

            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            <2009年2月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            1234567

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            久久精品无码一区二区三区日韩| 人妻精品久久无码专区精东影业 | 一级A毛片免费观看久久精品| 精品熟女少妇aⅴ免费久久| 天堂无码久久综合东京热| 久久精品免费全国观看国产| 伊人久久综合成人网| 久久99精品国产99久久| 一本大道久久东京热无码AV| 欧美亚洲色综久久精品国产| 国产精品亚洲综合专区片高清久久久| 亚洲乱码日产精品a级毛片久久 | 久久精品中文字幕久久| 久久国产影院| 久久99精品久久只有精品| 国产精品成人99久久久久91gav| 伊人久久无码精品中文字幕| 国产人久久人人人人爽| 久久久久高潮综合影院| 久久精品成人一区二区三区| 国产成人久久精品一区二区三区 | 亚洲国产成人乱码精品女人久久久不卡| 18禁黄久久久AAA片| 精品少妇人妻av无码久久| 亚洲国产精品一区二区久久| 亚洲中文字幕无码一久久区| 亚洲а∨天堂久久精品| 青青青国产精品国产精品久久久久| 伊人久久大香线蕉AV一区二区| 精品国产91久久久久久久| 婷婷久久五月天| 久久精品国产黑森林| 一本色道久久88加勒比—综合| 久久亚洲美女精品国产精品| 久久精品无码av| 久久久无码精品午夜| 天天影视色香欲综合久久| 久久精品女人天堂AV麻| 一本久久a久久精品综合夜夜| 国产91久久精品一区二区| 久久免费美女视频|