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

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            狠狠色丁香婷婷久久综合五月 | 伊人久久大香线蕉综合5g| 成人妇女免费播放久久久| 97超级碰碰碰久久久久| 曰曰摸天天摸人人看久久久| 亚洲国产精品综合久久一线| 伊人久久综合成人网| 国产成人久久激情91| 老司机午夜网站国内精品久久久久久久久 | 精品人妻伦一二三区久久| 国产精品久久久久久久人人看| 久久亚洲春色中文字幕久久久| 久久成人精品视频| 久久婷婷色综合一区二区| 伊人久久大香线蕉av不卡 | 亚洲精品久久久www| 久久久亚洲欧洲日产国码二区 | 国产一区二区精品久久岳| 天堂无码久久综合东京热| 久久精品国产亚洲综合色| 要久久爱在线免费观看| 国产精品一区二区久久精品无码| 天天躁日日躁狠狠久久| 久久夜色精品国产| 色综合合久久天天综合绕视看| 欧美亚洲国产精品久久| 久久久久亚洲爆乳少妇无| 久久精品国产亚洲av日韩| 久久精品国产亚洲AV香蕉| 久久精品国产福利国产琪琪| 精品久久久久久久| 久久精品国产免费一区| 久久精品国产亚洲AV大全| 精品无码久久久久国产动漫3d | 人妻精品久久久久中文字幕69| 亚洲国产精品狼友中文久久久 | 久久亚洲精品无码aⅴ大香| 久久久久久久亚洲精品| 国产精品VIDEOSSEX久久发布| 欧美日韩中文字幕久久伊人| 久久综合亚洲欧美成人|