• <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,不過幸好服務(wù)器沒掛。。。。。。
            代碼如下
            ?
            #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   博問   Chat2DB   管理


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

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            久久亚洲AV无码西西人体| 漂亮人妻被黑人久久精品| 一本色道久久88加勒比—综合| 嫩草影院久久99| 久久国产香蕉视频| 区久久AAA片69亚洲| 99久久精品日本一区二区免费| Xx性欧美肥妇精品久久久久久| 亚洲日本久久久午夜精品| 潮喷大喷水系列无码久久精品 | 精品久久久久久久国产潘金莲| 一本一本久久A久久综合精品| 亚洲国产精品一区二区久久| 亚洲欧美久久久久9999 | 国产亚州精品女人久久久久久 | 999久久久无码国产精品| 午夜精品久久久久久影视riav| 久久久久久久亚洲Av无码| 亚洲国产精品综合久久网络 | 久久99国产精品二区不卡| 国产欧美久久久精品影院| 久久久久久亚洲精品无码| 国产午夜福利精品久久2021| 综合人妻久久一区二区精品| 日本国产精品久久| 91久久九九无码成人网站| 国内精品久久久久久99蜜桃| 亚洲精品乱码久久久久久蜜桃不卡| 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲 | 亚洲中文字幕久久精品无码APP | 99久久久久| 狠狠干狠狠久久| 欧美精品久久久久久久自慰| 91麻豆国产精品91久久久| 久久影院亚洲一区| 亚洲欧洲久久久精品| 欧美色综合久久久久久| 三级片免费观看久久| 久久婷婷是五月综合色狠狠| 香蕉99久久国产综合精品宅男自 | 国内精品免费久久影院|