• <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 1727 Advanced Causal Measurements (ACM) 二分+貪心可行性判斷

            題目說的有點詭異,一開始沒想到二分,想直接通過半平面交來解或者是線性規劃。。。
            描述下題目平面上有一些點(x,t)(題目中描述的是(t,x),然后t是縱坐標,有點不舒服),然后滿足t2 >= t1+|x2-x1|的點(t1,x1)稱為點(x2,t2)的前導點。現在知道平面點集以及其前導點的個數,問其前導點集中t的最大值。
            根據不等式,可以發現每個點的前導點集范圍是一個以該點為頂點的三角形區域(根據不等式約束畫個圖看看就明白了),然后可以通過二分求得t,關于判斷當前t的可行性,將每個點表示為合法區間[x2-(t2-t1),x2+t2-t1],然后求這些區間的最小覆蓋數(就是求得一些子區間,使得這些子區間包含于原區間)。這個問題可以通過貪心算法,以區間右端點為第一關鍵字,左端點為第二關鍵字進行排序,然后每次貪心的選擇當前區間的右端點作為子區間,統計要導出全部區間需要子區間的個數num。
            代碼如下:
             1 import java.io.*;
             2 import java.util.Arrays;
             3 public class Main {
             4 
             5     /**
             6      * @param args
             7      */
             8     static StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
             9     //static StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(new FileInputStream("input.txt"))));
            10     static final int readInt() throws Exception
            11     {
            12         in.nextToken();
            13         return (int)in.nval;
            14     }
            15     static class node implements Comparable<node>
            16     {
            17         int t,x,s,e;
            18         public int compareTo(node pos)
            19         {
            20             if(e!=pos.e) return e-pos.e;
            21             else return s-pos.s;
            22         }
            23     }
            24     static node data[]=new node[100005];
            25     public static void main(String[] args) throws Exception{
            26         int n=readInt();
            27         for(int i=0;i<100005;i++)
            28             data[i]=new node();
            29         for(int test=1;test<=n;test++)
            30         {
            31             int num=readInt(),limit=readInt(),e=4000000,s=-4000000;
            32             for(int i=0;i<num;i++)
            33             {
            34                 data[i].t=readInt();
            35                 data[i].x=readInt();
            36                 e=Math.min(e, data[i].t);
            37             }
            38             while(s<=e)
            39             {
            40                 int mid=(s+e)>>1,count=1;
            41                 for(int i=0;i<num;i++)
            42                 {
            43                     data[i].s=data[i].x-data[i].t+mid;
            44                     data[i].e=data[i].x+data[i].t-mid;
            45                 }
            46                 
            47                 Arrays.sort(data,0,num);
            48                 int laste=data[0].e;
            49                 for(int i=1;i<num;i++)
            50                     if(data[i].s<=laste)
            51                         continue;
            52                     else
            53                     {
            54                         count++;
            55                         laste=data[i].e;
            56                     }
            57                 if(count<=limit)
            58                     s=mid+1;
            59                 else
            60                     e=mid-1;
            61             }
            62             System.out.println("Case "+test+""+e);            
            63         }
            64 
            65     }
            66 
            67 }
            68 

            posted on 2010-10-20 00:36 yzhw 閱讀(365) 評論(0)  編輯 收藏 引用 所屬分類: searchnumberic

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            色婷婷综合久久久中文字幕| 999久久久国产精品| 久久免费视频1| 狠狠色狠狠色综合久久| 色综合久久中文字幕无码| 欧美日韩中文字幕久久伊人| 天天久久狠狠色综合| 人妻系列无码专区久久五月天| 久久亚洲AV无码精品色午夜麻豆| 久久丫精品国产亚洲av不卡 | 伊人久久一区二区三区无码| 久久久久久久91精品免费观看| 色欲综合久久躁天天躁蜜桃| 国产69精品久久久久99| 久久精品国产99国产精品亚洲| 日本久久久精品中文字幕| 久久久久亚洲av成人网人人软件| 国产精品久久久久无码av| 久久综合亚洲鲁鲁五月天| 久久精品成人欧美大片| 国产精品久久久久AV福利动漫| 久久天天婷婷五月俺也去| 久久久久国产视频电影| 91精品无码久久久久久五月天| 九九久久自然熟的香蕉图片| 国产精品久久久久久久人人看| 久久99精品久久久久久噜噜 | 久久www免费人成精品香蕉| 久久精品国产99国产精品澳门| 天堂久久天堂AV色综合| 国产成人精品综合久久久久| 天天做夜夜做久久做狠狠| 久久国产精品偷99| 精品久久久久久无码人妻热| 欧美777精品久久久久网| 久久精品国产69国产精品亚洲| 国内精品久久久久影院优| 国产精品久久久久jk制服| 国产91久久精品一区二区| 久久久久久国产精品美女| 精品国产乱码久久久久久呢|