• <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)論排行榜

            久久久久久伊人高潮影院| 久久国产劲爆AV内射—百度| 麻豆亚洲AV永久无码精品久久| 思思久久好好热精品国产 | 99re这里只有精品热久久| 国产成人AV综合久久| 日韩久久久久久中文人妻 | 四虎国产精品成人免费久久| 99久久精品免费看国产一区二区三区| 久久久中文字幕| 日本欧美久久久久免费播放网| 久久免费视频观看| 久久精品国产亚洲av麻豆图片| 久久免费视频网站| 久久A级毛片免费观看| 久久久久亚洲AV无码网站| 久久www免费人成看国产片| 久久免费小视频| 久久男人Av资源网站无码软件| 久久这里只有精品视频99| 久久精品成人一区二区三区| 国产福利电影一区二区三区久久久久成人精品综合 | 久久久无码精品亚洲日韩蜜臀浪潮| 99久久婷婷免费国产综合精品| 亚洲国产精品无码久久久久久曰| 性欧美大战久久久久久久| 久久成人国产精品二三区| 精品久久久久久久久久久久久久久| 亚洲AV无码久久精品蜜桃| 99国产欧美精品久久久蜜芽| 久久精品国产男包| 中文字幕精品无码久久久久久3D日动漫| 国产精品岛国久久久久| 久久国产精品99精品国产| 一本一本久久A久久综合精品| 伊人精品久久久久7777| 久久亚洲精品国产亚洲老地址| 久久国产精品国语对白| 久久艹国产| 天堂无码久久综合东京热| 一本色道久久88综合日韩精品 |