Stall Reservations
原文是English，这里直接上中文吧
Descriptions:
这里有N只 (1 <= N <= 50,000) 挑剔的奶牛! 他们如此挑剔以致于必须在[A,B ]的时间内产奶(1 <= A <= B <= 1,000,000)当然, FJ必须为他们创造一个决定挤奶时间的系统.当然，没有牛想与其他奶牛分享这一时光
帮助FJ做以下事:
- 使每只牛都有专属时间的最小牛棚数
- 每只牛在哪个牛棚
也许有很多可行解。输出一种即可，采用SPJ
Input
第一行一个数字 N
第 2..N+1行: 第 i+1行 描述了i号奶牛挤奶的起止时间
Output
第一行：牛棚最小数量
Lines 2..N+1: 第 i+1行 描述了i奶牛被安排的牛棚
Sample Input
5
1 10
2 4
3 6
5 8
4 7
Sample Output
4
1
2
3
2
4
题目链接：
这题考查的是贪心算法，做这题要考虑两点：1、要对母牛开始挤奶的时间进行排序。2、要知道畜栏是否能使用，在没有合适畜栏的时候加上一个。
首先，把所有奶牛按挤奶开始时间从小到大排序。
然后，为第一头奶牛分配一个畜栏。
最后，依次处理后面每头奶牛i。处理i时,考虑已分配畜栏中,结束时间最早的畜栏x。如何处理详情见代码
露要用优先队列存放已经分配的畜栏,并使得结束时间最早的畜栏始丝列头部
AC代码：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define ME0(x) memset(x,0,sizeof(x))
using namespace std;
struct cow//奶牛
{
int s,e;//挤奶时间的开始与结束
int no;//奶牛编号
//以挤奶时间小的规则排序
bool operator < (const cow & c) const
{
return s<c.s;
}
};
cow cows[];
int pos[];//记录每头牛在哪个畜栏
struct stall//畜栏
{
int over;//畜栏使用结束时间
int No;//畜栏编号
//以畜栏使用结束时间小的规则排序
bool operator<(const stall & c) const
{
return over>c.over;//优先队列排序相反
}
stall(int over,int No):over(over),No(No){}
};
priority_queue<stall> q;//优先队列
int main()
{
int N;
int total=;//总的畜栏数
cin>>N;
for(int i=; i<N; ++i)
{
cin>>cows[i].s>>cows[i].e;
cows[i].no=i;
}
sort(cows,cows+N);
// for(int i=0; i<N; i++)
// cout<<cows[i].s<<cows[i].e<<endl;
for(int i=; i<N; ++i)
{
if(q.empty())//没有畜栏的情况
{
++total;
q.push(stall(cows[i].e,total));
pos[cows[i].no]=total;
}
else
{
stall st=q.top();
if(st.over<cows[i].s)//有畜栏且畜栏结束使用时间小于奶牛开始挤奶的时间
{
q.pop();
q.push(stall(cows[i].e,st.No));
pos[cows[i].no]=st.No;
}
else//有畜栏且畜栏结束使用时间大于/等于奶牛开始挤奶的时间
{
++total;//新增一个畜栏
q.push(stall(cows[i].e,total));
pos[cows[i].no]=total;
}
}
}
cout<<total<<endl;
for(int i=; i<N; ++i)
cout<<pos[i]<<endl;
}