POJ 3190 Stall Reservations-奶牛分欄（區間貪心，優先隊列）
http://poj.org/problem?id=3190
題目大意：每一只奶牛要求在時間區間[A,B]內獨享一個牛欄。問最少需要多少個牛欄。
貪心策略是優先滿足A最小的奶牛，維持一個牛欄B最小堆，將新來的奶牛塞進B最小的牛欄裡。
#include
#include
#include
using namespace std; struct Section{ unsigned int index; unsigned int begin;
unsigned int end; bool operator < (const Section& b) const { return begin < b.begin; } }; struct Stall{ unsigned int id; unsigned int end; bool operator < (const Stall& b) const { return end > b.end; } Stall(){} Stall(unsigned int id, unsigned int end):id(id),
end(end){}}; #define MAX_COWS 50000Section cow[MAX_COWS];unsigned int result[MAX_COWS]; // 每頭牛從屬於哪個牛欄priority_queue que; // 最小堆，儲存所有牛欄區間的結束點（也就是最右端） inline void put_cow(const int& i, const bool& new_stall){ Stall s; if (new_stall) { s.id = que.size()
+ 1; } else { s.id = que.top().id; que.pop(); } s.end = cow[i].end; result[cow[i].index] = s.id; que.push(s);} ///////////////////////////SubMain//////////////////////////////////int main(int argc, char *argv[]){#ifndef ONLINE_JUDGE freopen("in.txt", "r",
stdin); freopen("out.txt", "w", stdout);#endif int N; cin >> N; for (int i = 0; i < N; ++i) { cow[i].index = i; cin >> cow[i].begin; cin >> cow[i].end; } sort(cow, cow + N); put_cow(0, true); for (int i = 1; i < N; ++i) { put_cow (i, cow[i].begin <= que.top().end);
} cout << que.size() << endl; for (int i = 0; i < N; ++i) { cout << result[i] << endl; }#ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt");#endif return 0;}///////////////////////////End Sub//////////////////////////////////
代碼二
對cow進行排列。按L以及R從小到大排序。確保遍歷的時候優先取到最小的L.
然後就可以對cow遍歷求解。
#include
#include
#include
#include
using namespace std;
struct N
{
int l,r,id,stall;
bool operator <(const N &a)const
{
return a.rque;
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>cow[i].l>>cow[i].r;
cow[i].id=i;
}
sort(cow+1,cow+n+1,cmp);
cow[0].stall=1;
cow[0].r=0;
que.push(cow[0]);
int a[50010];
int S=2;
for(int i=1;i<=n;i++)
{
N c=que.top();
if(cow[i].l>c.r)
{
que.pop();
cow[i].stall=c.stall;
a[cow[i].id]=c.stall;
que.push(cow[i]);
}
else
{
cow[i].stall=S;
a[cow[i].id]=S++;
que.push(cow[i]);
}
}
cout<
華麗的分界線。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
對於這個題目，已知有兩種貪心策略是正確的。
- 將
頭牛按照開始時間 
排序，每次選取牛集合 
中的開始時間最早，並且與結束時間 
不沖突的元素，找到之後從集合 中刪除或者標記元素。當找不到滿足開始時間 大於 結束時間這一條件的元素時，重新從 中選取元素，直到 為空。 - 將 頭牛按照開始時間 排序，首先將第一頭牛存入集合
中，如果接下來的牛滿足開始時間大於 中最早結束時間，那麼取出這個元素，並更新其時間結束時間為當前牛的結束時間，然後重新存入集合中。否則直接將該當前牛存入集合中。
2.2 貪心算法證明
貪心算法的證明主要是兩種思路。
第一種 方法被稱為 staying ahead [2]，即保持領先，意義為如果我們運用某個策略，在算法的每一步中都使某個條件保持領先，那麼最後可以利用這個領先條件來證明最優解。這種方法本質上結合了上面介紹的Induction和Contradiction方法。
接下來我們將這個方法應用到POJ 3190算法2的證明中。
- 首先，我們需要確定一個領先條件，我們設這個領先條件為：在算法的每一步中，都選取最小開始時間的畜欄放入下一頭牛。即
， 
代表當前策略，
代表最優策略，對於貪心算法的證明，基本假設是 當前貪心策略至少和最優策略保證相同的效果 。 - 證明這個條件在算法的每一步中都成立。運用Induction method，首先證明base case的情況，我們首先從開始時間0開始存入牛，所以顯然成立。接下來，證明前k頭牛時成立，k+1時也成立。兩種情況，第k+1頭牛的開始時間
小於 集合 中的最小結束時間，那麼直接存入集合，這個時候要麼最小時間更新為第 
頭牛的結束時間，要麼保持原來的結束時間。否則，如果第k+1頭牛的開始時間 大於 集合 中的最小結束時間，更新集合 最小結束時間元素信息。因此接下來仍然可以直接選取最小結束時間的畜欄。 - 接下來我們運用Contradiction method來證明我們的策略可以得到畜欄數最少的解決方案。由於我們已經證明每一步必定可選最小開始時間的畜欄，所以如果上述策略不成立，最優解 中一定存在某一畜欄，其中所有牛都可以被放入其他畜欄。那麼，這些牛同樣可以被放入到貪心策略解的畜欄中（因為我們證明了每一步選取的最小開始時間至少和最優解一致）。然而，在放入某一頭牛的時候，如果其開始時間 大於 最小結束時間，那麼一定已經被放入到之前的畜欄中去了，所以判定這些牛一定不能放入到原有的畜欄中去。
- 至此，證明結束。算法2可以得到最優解。
第二種 方法被稱為 exchange arguments [2]，即將最優解元素和當前貪心策略解元素逐個交換，交換的情況很多種[3]，可以是
中存在的元素， 中不存在，也可以是順序不同，如果不影響最優解效果，那麼貪心策略成立。在我們的題目中，交換條件可以是 放的畜欄不同 。我們已知算法2是最優解，來證明算法1也是最優解。
交換
與 中的元素， ， 中如果存在放入的畜欄不同，只有一種情況：
c1 -------------|t1
c2 -------|t2
如果當前牛的開始時間 
，算法1將不會處理這個元素，而是在第二輪中將這個元素放入到 
中，而算法2直接將當前元素放入 ，這種情況下兩種算法結果相同。
如果當前牛的開始時間 
，算法1將元素放入 
，然而算法2會將元素放入 。但是這樣的處理不會影響最優解，算法將元素放入到 後， 也就一定只能存入開始時間在 
之後的元素，其他開始時間在 之前的元素將會被放入 。
c1 -------------|t1
c2 -------|t2 ------------|t3
而對於算法1而言：
c1 -------------|t1-----------|t3
c2 -------|t2
其他開始時間在
之前的元素將會被放入 ，並且這些元素的開始時間一定 ，所以放入 和放入 對算法最終的效果沒有影響。因此，貪心策略成立
2.3 時間復雜度分析
下面簡單分析一下這個題目的三種解法：
。遍歷復雜度，我們假設最壞情況，每次遍歷刪除一個元素： 
。遍歷，同樣是最壞情況，每次前進一個元素（二分查找）：
