題目鏈接：點擊查看

題目大意：有n頭牛在畜欄中吃草，每個畜欄在同一時間段只能提供給一頭牛吃草，所以可能會需要多個畜欄，給定N頭牛和每頭牛開始吃草和結束吃草的時間，每頭牛在給定時間段內會一直吃草，求需要的最小畜欄數目和每頭牛對應的畜欄方案

題目分析：如果這個題目不要求方案的話，我是想用差分來做的，對于每個時間段我們讓其中的數量+1，最后跑一遍前綴和答案就出來了，但是這個題讓求方案，再用差分的話就略顯啰嗦了，這里先想一下最基本的貪心策略

我們肯定要根據每頭牛開始吃草的時間升序排序，依次處理每一頭奶牛，在處理當前奶牛的時候，我們可以依次遍歷一遍每一個畜欄，判斷一下是否有奶牛已經吃完草了，這樣我們就可以將當前奶牛加入到這個畜欄中去了，這里需要注意一下，判斷是否吃完草的條件是當前奶牛的開始時間需要大于畜欄中奶牛的結束時間，而不是大于等于，如果所有畜欄中的奶牛都沒有結束，那么就只能新建一個畜欄給當前奶牛吃草了

上面的貪心策略，理論上是正確的，但時間復雜度到了n*n，對于這個題目而言我們還需要優化，我們可以對于第二層循環找是否有已經結束的奶牛這里，用優先隊列進行優化，可以將結束時間早的奶牛放在堆頂，維護的時間為nlogn，判斷的時間為O(1)，這樣就能以nlogn的時間復雜度完成上面的貪心了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=5e4+100;int ans[N];struct Cow {int l,r,id;bool operator<(const Cow& a)const//維護優先隊列的小頂堆{return r>a.r;} }cow[N];bool cmp(Cow a,Cow b)//對奶牛的開始時間升序排序 {return a.l<b.l; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;while(scanf("%d",&n)!=EOF){priority_queue<Cow>q;for(int i=1;i<=n;i++){scanf("%d%d",&cow[i].l,&cow[i].r);cow[i].id=i;}sort(cow+1,cow+1+n,cmp);int cnt=0;for(int i=1;i<=n;i++)//依次處理每個奶牛{if(q.size()&&q.top().r<cow[i].l)//如果有結束的奶牛，那就將當前奶牛放到結束奶牛的位置{ans[cow[i].id]=ans[q.top().id];q.pop();}else//否則新建一個畜欄{ans[cow[i].id]=++cnt;}q.push(cow[i]);}printf("%d\n",cnt);for(int i=1;i<=n;i++)printf("%d\n",ans[i]);}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 3190 Stall Reservations(贪心+优先队列优化)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。