AcWing 111. 畜栏预定
原题链接
简单
作者:
烟花易冷
,
2020-08-11 23:04:16
,
所有人可见
,
阅读 682
代码就是yxc大佬的代码,我来贴个注释
// 贪心
// 首先明确两个容易想歪的地方:
// 1.cows[N]的结构是{{开始时间,结束时间},牛的编号},而优先队列的结构是{结束时间,畜栏数序号}
// 2.需要几个畜栏,我们就在堆里造几个pll,只保留每个畜栏最后一个元素的结束时间,然后不停更新结束时间
// 应该没什么问题了
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 50010;
int n;
int id[N];
pair<PII, int> cows[N];
priority_queue<PII, vector<PII>, greater<PII>> heap;//优先队列声明小顶堆
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ )
{
cin >> cows[i].first.first >> cows[i].first.second;// 开始时间&结束时间
cows[i].second = i;// 编号
}
sort(cows, cows + n);// 开始时间排序
for (int i = 0; i < n; i ++ )
{
if (heap.empty() || heap.top().first >= cows[i].first.first)// 堆为空或 堆顶元素结束时间大于当前元素的开始时间
{
PII stall = {cows[i].first.second, heap.size()};// 新建pll,放入当前元素结束时间与畜栏数序号
id[cows[i].second] = stall.second;// 记录编号
heap.push(stall);// stall入堆
}
else
{
auto stall = heap.top();// 保存堆顶元素
heap.pop();// 取出堆顶元素销毁
stall.first = cows[i].first.second;// 更新结束时间
id[cows[i].second] = stall.second;// 记录编号
heap.push(stall);// stall入堆
}
}// 每次入堆后,堆顶元素一定是结束时间最小的那个
cout << heap.size() << endl;// 畜栏数
for (int i = 0; i < n; i ++ )
cout << id[i] + 1 << endl;
return 0;
}