題目：http://poj.org/problem?id=2456
Farmer John的乳牛們是很Aggressive的
現在數線上有N(100000)個牛舍一字排開
一個牛舍可以裝一隻牛
以及現在想要放M隻牛進去
牛之間的距離越近的話就越容易幹架(真是Aggressive)
所以FJ希望牛之間隔的越遠越好，也就是找出一種分配方案
使得最近的牛隻之間間隔距離可以最大化
輸出這個值
程式碼：(codepad掛了，待補)
「使得最小的…最大」
二分答案能求解的問題就是有這種代表性
說起來就是二分+貪心
對於某個最近距離Mid，想要知道是否有分配方案能滿足的話
方法就是(排序過牛欄由左至右)，從最左開始選、接下來往右找一個最近合法的牛欄
如果放不足M隻那就是這個距離不可行、必須下修
感性的說明這樣的貪心性質：
選越靠左邊的越好，因為可選集合是有限的
如果當前選擇同時有x1和x2能滿足條件、而x1<x2
那麼選了x2勢必會壓縮到下次選擇的空間，結果肯定只會更爛、有更右邊的x3,x4,...同理
沒有留言:
張貼留言