前言
链接
解法
一上来就看出是一道shabi贪心题,需要对开始时间拍一下序,暴力的复杂度 \(O\) 不知道能不能过;
暴力
维护一个数组 \(h\) ,令记录每个栅栏安排的最后一只牛,每次扫描数组,找到栅栏中吃完草结束时间最早的,如果该牛开始时间大于最早的,则踢出吃完的牛,将该牛放进去;
如果不存在上面的情况,则新建一个栅栏;
优秀解法
用小根堆优化栅栏数组最小值,时间复杂度 \(O\)
Code
#include<bits/stdc++.h>
using std::queue;
using std::endl;
using std::priority_queue;
using std::pair;
using std::sort;
using std::make_pair;
#define pq priority_queue
#define ri register int
#define il inline
#define mp make_pair
const int maxn = 5e4 + 100;
typedef long long ll;
int n, cnt, house;
struct node
{
int a, b, id, ak;
bool operator <(const node &u)const
{
return a<u.a;
}
}cow[maxn];
bool cmp(node i, node j)
{
return i.id<j.id;
}
pq< pair< int ,int > > rank;
int read()
{
int x = 0, ch = getchar(), f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = read(); ++cnt;
for( ri i = 1; i <= n; ++ i) cow[i].a = read(), cow[i].b = read(), cow[i].id = i;
sort(cow + 1, cow + 1 + n);
cow[1].ak = 1;
rank.push(mp(-cow[1].b,++house));
for(ri i = 2; i <= n; ++ i)
{
if(cow[i].a > -rank.top().first)
{
cow[i].ak = rank.top().second;
rank.push(mp(-cow[i].b,rank.top().second));
rank.pop();
}
else
{
rank.push(mp(-cow[i].b, ++cnt));
cow[i].ak = cnt;
}
}
sort(cow + 1, cow + 1 + n, cmp);
printf("%d\n",cnt);
for(ri i = 1; i <= n; ++ i ) printf("%d\n",cow[i].ak);
return 0;
}