题目大意：一群牛很挑剔，他们仅在一个时间段内挤奶，而且只能在一个棚里面挤，不能与其他牛共享地方，现在给你一群牛，问你如果要全部牛都挤奶，至少需要多少牛棚?
这一题如果把时间区间去掉，那就变成装箱子问题了（装箱子要用Splay维护），但是现在规定了区间和时间，我们只用贪婪算法就可以了，每次只用找到最小就可以了（用堆维护）。
PS：一开始我想到用AVL去维护，的都不知道我在想什么，简直浪费时间
#include <iostream>
#include <functional>
#include <algorithm> using namespace std; typedef struct iterval
{
int cows_num;
int Which_Stall;
int start;
int end;
}Cow;
typedef struct box
{
int box_num;
int min_t;
}Stall;
typedef int Position;
int fcomp1(const void *a, const void *b)
{
return (*(Cow *)a).start - (*(Cow *)b).start;
}
int fcomp2(const void *a, const void *b)
{
return (*(Cow *)a).cows_num - (*(Cow *)b).cows_num;
} static Cow cows_set[];
static Stall s_heap[];
static int sum_of_stalls; void Search(const int);
void Insert(Stall, Position);
Stall Delete_Min(void); int main(void)//这一题用堆维护
{
int n;
while (~scanf("%d", &n))
{
for (int i = ; i < n; i++)
{
scanf("%d%d", &cows_set[i].start, &cows_set[i].end);
cows_set[i].cows_num = i;
}
qsort(cows_set, n, sizeof(Cow), fcomp1);
Search(n);
}
return ;
} void Insert(Stall goal, Position pos)
{
Position s = pos, pr; for (; s > ; s = pr)//上滤
{
pr = s % == ? s >> : (s - ) >> ;
if (s_heap[pr].min_t > goal.min_t)
s_heap[s] = s_heap[pr];
else break;
}
s_heap[s] = goal;
} Stall Delete_Min(void)
{
Stall mins_stalls = s_heap[],tmp = s_heap[sum_of_stalls--];
Position pr, s1, s2; for (pr = ; pr <= sum_of_stalls;)
{
s1 = pr << ; s2 = s1 + ;
if (s2 <= sum_of_stalls)
{
if (s_heap[s1].min_t < s_heap[s2].min_t){
s_heap[pr] = s_heap[s1]; pr = s1;
}
else{
s_heap[pr] = s_heap[s2]; pr = s2;
}
}
else
{
if (s1 <= sum_of_stalls){
s_heap[pr] = s_heap[s1]; pr = s1;
}
break;
}
}
Insert(tmp, pr);
return mins_stalls;
} void Search(const int n)
{
Stall tmp;
sum_of_stalls = ;
tmp.box_num = ; tmp.min_t = cows_set[].end;
Insert(tmp, );
cows_set[].Which_Stall = ; for (int i = ; i < n; i++)
{
if (cows_set[i].start <= s_heap[].min_t)//放不下
{
tmp.box_num = ++sum_of_stalls; tmp.min_t = cows_set[i].end;
Insert(tmp, sum_of_stalls);
cows_set[i].Which_Stall = sum_of_stalls;
}
else
{
tmp = Delete_Min();
tmp.min_t = cows_set[i].end;
cows_set[i].Which_Stall = tmp.box_num;
Insert(tmp, ++sum_of_stalls);
}
}
printf("%d\n", sum_of_stalls);
qsort(cows_set, n, sizeof(Cow), fcomp2);
for (int i = ; i < n; i++)
printf("%d\n", cows_set[i].Which_Stall);
}