POJ 3190
题意N 头牛在畜栏中吃草 ，每个畜栏在同一时间段只能给一头牛吃, 2 -4 和 4 - 9必须要两个畜栏,给N头牛吃草和结束吃草时间
求最小畜栏数和每头牛吃的栏编号
一开始写了个n^2 暴力去统计超时
然后我们想到要用小根堆(优先队列放负数) 去优化
那么时间复杂度就降为O(nlogn)然后就可以过了
#include <cstdio> #include <queue> #include <stack> #include <map> #include <sstream> #include <iostream> #include <algorithm> #include <set> #include <cmath> #include <vector> using namespace std; const int MAX_N = 50024; int ans[MAX_N],now[MAX_N]; struct node { int l,r,id; bool operator < (const node other) const { if(l==other.l) return r<other.r; return l < other.l; } }arr[MAX_N]; priority_queue<pair<int ,int > > q; int main(){ int n,use = 0; while(scanf("%d",&n)!=EOF){ while(!q.empty()) q.pop(); use = 0; for(int i = 1;i<=n;++i) { scanf("%d%d",&arr[i].l,&arr[i].r); arr[i].id = i; } sort(arr+1,arr+1+n); for(int i = 1;i<=n;++i){ if(!q.empty()){ int top = -q.top().first; int id = q.top().second; //cout << " top = " << top <<endl; //cout << "arr[i].l = " <<arr[i].l << endl; while(top<arr[i].l){ now[ans[id]] = 0; q.pop(); if(q.empty()) break; top = -q.top().first; id = q.top().second; //cout <<" top = "<<top <<"id = " << id<< endl; //cout <<"arr[i].l = " <<arr[i].l << endl; } } //cout << "use = " <<use << " q.size() = " << q.size() << endl; if(use-q.size()>0){ for(int j = 1;j<=use;++j){ if(!now[j]){ now[j] = 1; ans[arr[i].id] = j; q.push(make_pair(-arr[i].r,arr[i].id)); break; } } } else { use++; ans[arr[i].id] = use; q.push(make_pair(-arr[i].r,arr[i].id)); now[use] = 1; } } printf("%d\n",use); for(int i = 1;i<=n;++i) printf("%d\n",ans[i]); } return 0; }
