• <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>

            pku 2464 掃描線+離散化+樹狀數組(線段樹、平衡樹)

            題意是這樣,平面上有很多點,過一點的十字交叉線將平面分為4個部分,求某條掃描線的使得左下平面和右上平面中的點的最小值最大。
            這道題比較有意思,用2個樹結構進行維護,左邊的樹為空,右邊的樹包含所有點,按照點的x、y坐標排序,一個掃面線過去,左邊的樹增加點,右邊的樹刪除點,進行動態統計~。至于樹結構什么都可以,直接套set估計也能過,由于我在做線段樹、樹狀數組專題,就用樹狀數組來實現吧,不過需要離散化,55
            貼代碼
              1 import java.io.*;
              2 import java.util.*;
              3 public class Main {
              4 
              5     /**
              6      * @param args
              7      */
              8     static int arr1[]=new int[200005],arr2[]=new int[200005],n,c;
              9     static class node implements Comparable<node>
             10     {
             11         int x,y;
             12         public int compareTo(node pos)
             13         {
             14             if(x!=pos.x)
             15                  return x-pos.x;
             16             else
             17                  return y-pos.y;
             18         }
             19     }
             20     static void add(int pos,int val,int arr[])
             21     {
             22         for(;pos<=n;pos+=pos&(-pos))
             23               arr[pos]+=val;
             24     }
             25     static int sum(int pos,int arr[])
             26     {
             27         int res=0;
             28         for(;pos>0;pos-=pos&(-pos))
             29             res+=arr[pos];
             30         return res;
             31     }
             32     static TreeMap<Integer,Integer> refer=new TreeMap<Integer,Integer>();
             33     static node data[]=new node[200005];
             34     static ArrayList<Integer> tres=new ArrayList<Integer>(),res=new ArrayList<Integer>();
             35     public static void main(String[] args) throws IOException{
             36         StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
             37         for(int i=0;i<=200000;i++)
             38             data[i]=new node();
             39         while(true)
             40         {
             41             in.nextToken();
             42             n=(int)in.nval;
             43             if(n==0break;
             44             refer.clear();
             45             for(int i=0;i<n;i++)
             46             {
             47                 in.nextToken();
             48                 data[i].x=(int)in.nval;
             49                 in.nextToken();
             50                 data[i].y=(int)in.nval;
             51                 refer.put(data[i].y, 0);
             52             }
             53             Set<Integer> tmp=refer.keySet();
             54             c=1;
             55             Arrays.fill(arr1, 0);
             56             Arrays.fill(arr2, 0);
             57             Arrays.sort(data, 0, n);
             58             for(Integer p:tmp)
             59                refer.put(p, c++);
             60             c--;
             61             for(int i=0;i<n;i++)
             62             {
             63                 data[i].y=refer.get(data[i].y);
             64                 add(data[i].y,1,arr2);
             65             }
             66             tres.clear();
             67             res.clear();
             68             int value=0,minvalue=Integer.MAX_VALUE;
             69             int lastx=data[0].x,begin=0;
             70             for(int i=0;i<n;i++)
             71             {
             72                 if(data[i].x!=lastx)
             73                 {
             74                     for(int j=begin;j<i;j++)
             75                     {
             76                         add(data[j].y,-1,arr2);
             77                     }
             78                     for(int j=begin;j<i;j++)
             79                     {
             80                         minvalue=Math.min(minvalue, sum(data[j].y-1,arr1)+sum(c,arr2)-sum(data[j].y,arr2));
             81                         tres.add(sum(c,arr1)-sum(data[j].y,arr1)+sum(data[j].y-1,arr2));
             82                     }
             83                     for(int j=begin;j<i;j++)
             84                     {
             85                         add(data[j].y,1,arr1);
             86                     }
             87                     if(minvalue>value)
             88                     {
             89                         value=minvalue;
             90                         res.clear();
             91                         res.addAll(tres);
             92                     }
             93                     else if(minvalue==value)
             94                         res.addAll(tres);
             95                     tres.clear();
             96                     begin=i;
             97                     lastx=data[i].x;
             98                     minvalue=Integer.MAX_VALUE;
             99                 }
            100             }
            101             if(res.isEmpty()) res.add(0);
            102             System.out.print("Stan: "+value+"; Ollie: ");
            103             Collections.sort(res);
            104             System.out.print(res.get(0));
            105             for(int i=1;i<res.size();i++)
            106                 if(!res.get(i).equals(res.get(i-1)))
            107                     System.out.print(" "+res.get(i));
            108             System.out.println(";");
            109             
            110         }
            111 
            112     }
            113 
            114 }
            115 


            posted on 2010-10-28 01:26 yzhw 閱讀(329) 評論(0)  編輯 收藏 引用 所屬分類: data struct

            <2010年10月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            国产精品成人无码久久久久久 | 久久精品无码一区二区app| 久久香蕉国产线看观看精品yw| 久久无码AV中文出轨人妻| 欧美日韩精品久久久免费观看 | 欧美日韩精品久久久久| 久久天天躁夜夜躁狠狠| 亚洲精品乱码久久久久久按摩 | 久久精品国产99久久香蕉| 色天使久久综合网天天| 18禁黄久久久AAA片| 97热久久免费频精品99| 性欧美大战久久久久久久| 精品久久久噜噜噜久久久| 色婷婷噜噜久久国产精品12p| 人妻无码αv中文字幕久久琪琪布 人妻无码久久一区二区三区免费 人妻无码中文久久久久专区 | 午夜精品久久久久久久无码| 日韩精品久久无码中文字幕| 亚洲国产精久久久久久久| 久久国语露脸国产精品电影| 国产精品久久久久久久午夜片 | 国产香蕉97碰碰久久人人| 久久九九兔免费精品6| 精品久久人人妻人人做精品| 亚洲色欲久久久综合网东京热| 久久久久99精品成人片牛牛影视| 国产精品久久午夜夜伦鲁鲁| 亚洲AV无码久久精品狠狠爱浪潮| 亚洲精品乱码久久久久久蜜桃| 97超级碰碰碰碰久久久久| 国产精品久久一区二区三区| 热re99久久精品国99热| 狠狠综合久久综合88亚洲| 欧美久久一区二区三区| 品成人欧美大片久久国产欧美... 品成人欧美大片久久国产欧美 | 日本道色综合久久影院| 99久久综合狠狠综合久久止| 久久婷婷国产综合精品| 亚洲色欲久久久综合网东京热| 精品综合久久久久久98| 97香蕉久久夜色精品国产|