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

            深夜久久AAAAA级毛片免费看| 四虎国产精品成人免费久久| 97久久精品人妻人人搡人人玩| 麻豆亚洲AV永久无码精品久久| 99久久久精品免费观看国产| 韩国三级中文字幕hd久久精品 | 国产99久久久国产精免费| 精品久久久久久无码人妻热| 伊人久久亚洲综合影院| 国产精品美女久久久m| 久久这里有精品| 99热热久久这里只有精品68| 亚洲中文字幕无码久久综合网| 夜夜亚洲天天久久| 色妞色综合久久夜夜| 久久亚洲国产成人精品无码区| 俺来也俺去啦久久综合网| 亚洲精品午夜国产va久久| 日韩亚洲欧美久久久www综合网| 开心久久婷婷综合中文字幕| 蜜桃麻豆WWW久久囤产精品| 国内精品久久久久久久久| 久久99久久99精品免视看动漫| 日韩久久无码免费毛片软件| 久久久青草久久久青草| 久久久国产乱子伦精品作者| 久久久精品国产免大香伊| 久久九九兔免费精品6| 久久精品无码一区二区app| 国产综合精品久久亚洲| 99久久无码一区人妻a黑| 久久精品人成免费| 久久亚洲AV成人出白浆无码国产| 亚洲国产成人精品91久久久| 国产农村妇女毛片精品久久| 久久91精品国产91久久小草| 久久99国产综合精品| 日韩久久久久久中文人妻| 亚洲国产精品无码久久久蜜芽| 精品国产青草久久久久福利| 精品久久久久成人码免费动漫|