设计师招聘网站,免费的企业建站系统,沧州各种网站,网站建设企业开发Stall Reservations
luogu 2859
poj 3190
题目大意#xff1a;
有n头牛#xff0c;每头牛都有自己的挤奶时间#xff0c;挤奶时间内每头牛用一个奶棚#xff0c;现在问最少需要多少个奶棚
输入样例
5
1 10
2 4
3 6
5 8
4 7输出样例
4
1
2
3
2
4数据范围 1⩽N⩽50,00…Stall Reservations
luogu 2859
poj 3190
题目大意
有n头牛每头牛都有自己的挤奶时间挤奶时间内每头牛用一个奶棚现在问最少需要多少个奶棚
输入样例
5
1 10
2 4
3 6
5 8
4 7输出样例
4
1
2
3
2
4数据范围
1⩽N⩽50,0001 \leqslant N \leqslant 50,0001⩽N⩽50,000 1⩽A⩽B⩽1,000,0001 \leqslant A \leqslant B \leqslant 1,000,0001⩽A⩽B⩽1,000,000
解题思路
直接贪心当有位时就进去否则开一个但这样o(n2)o(n^2)o(n2)会TLETLETLE所以我们用STL堆来求空的使时间复杂度优化到o(nlogn)o(n\ log_n)o(n logn)
代码
#includequeue
#includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
int n,ans;
struct rec
{int s,bg,ed,num;
}a[50500];
bool operator (const rec x,const rec y){return x.edy.ed;}//改为小根堆
bool cmp(rec x,rec y){return x.bgy.bg;}
bool cmpp(rec x,rec y){return x.numy.num;}
int main()
{scanf(%d,n);for (int i1;in;i){scanf(%d %d,a[i].bg,a[i].ed);a[i].numi;}sort(a1,a1n,cmp);priority_queuerecd;//定义堆a[1].s1;d.push(a[1]);ans1;for (int i2;in;i){rec hd.top();if (h.eda[i].bg)//看看是否重复{d.pop();a[i].sh.s;//记录牛棚的编号d.push(a[i]);//入堆}else{a[i].sans;//新建一个牛棚d.push(a[i]);}}sort(a1,a1n,cmpp);//排序回原来的样子printf(%d\n,ans);for (int i1;in;i)printf(%d\n,a[i].s);
}
