链接:poj3190
Stall Reservations
**Time Limit:** 1000MS **Memory Limit:** 65536K **Total Submissions:** 4735 **Accepted:** 1688 Special Judge Description
Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= 1,000,000), which includes both times A and B. Obviously, FJ must create a reservation system to determine which stall each cow can be assigned for her milking time. Of course, no cow will share such a private moment with other cows.Help FJ by determining:
- The minimum number of stalls required in the barn so that each cow can have her private milking period
- An assignment of cows to these stalls over time
Many answers are correct for each test dataset; a program will grade your answer.
Input
Line 1: A single integer, NLines 2..N+1: Line i+1 describes cow i’s milking interval with two space-separated integers.
Output
Line 1: The minimum number of stalls the barn must have.Lines 2..N+1: Line i+1 describes the stall to which cow i will be assigned for her milking period.
Sample Input
5 1 10 2 4 3 6 5 8 4 7Sample Output
4 1 2 3 2 4Hint
Explanation of the sample:Here’s a graphical schedule for this output:
Time 1 2 3 4 5 6 7 8 9 10 Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>> Stall 2 .. c2>>>>>> c4>>>>>>>>> .. .. Stall 3 .. .. c3>>>>>>>>> .. .. .. .. Stall 4 .. .. .. c5>>>>>>>>> .. .. ..Other outputs using the same number of stalls are possible.
其实还是对堆的应用不熟练啊,
正确思路应该是首先建立一个结构体存储每个牛的产奶时间的左右端点,然后按照产奶开始时间从小到大排序,优先处理先开始产奶的奶牛,同时结构体内还需要一个变量记录每个牛的id,以便排序之后的处理和输出:
struct Cow
{
int l,r,co;
}c[maxn];
bool cmp(Cow c1,Cow c2){
if(c1.l==c2.l)return c1.r<c2.r;
else return c1.l<c2.l;
}
然后,建立一个表示stall的优先队列,这个优先队列每次先取出队列中最早结束的奶牛结构体Cow,
比如现在优先队列中有m头奶牛,对第m+1头奶牛,如果这头奶牛的开始时间小于等于优先队列中最早结束产奶的奶牛的结束时间,那么就需要增加一个stall,于是将这头奶牛加入优先队列;如果这头奶牛的开始时间大于上述时间,那么取出优先队列的top,并将这头奶牛加入队列,同时维护一个ans值和ansl数组以便输出.
对优先队列,应该首先对结构体的<运算符进行重载:
bool operator <(const Cow& a,const Cow& b)
{
if(a.r==b.r)return a.l>b.l;
else return a.r>b.r;
}
下面是完整AC代码:
/*
* Filename: poj3190d.cpp
* Desciption: 我要疯了,真的
* Created: 2016年03月11日 14时16分29秒 星期五
* Author: JIngwei Xu [mail:xu_jingwei@outlook.com]
*
*/
#include<bitset>
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<queue>
#define INT_MAX 1<<30
using namespace std;
typedef long long ll;
const int INF=0x7F;
int n;
const int maxn=50000+7;
int anl[maxn];
struct Cow
{
int l,r,co;
}c[maxn];
bool cmp(Cow c1,Cow c2){
if(c1.l==c2.l)return c1.r<c2.r;
else return c1.l<c2.l;
}
bool operator <(const Cow& a,const Cow& b)
{
if(a.r==b.r)return a.l>b.l;
else return a.r>b.r;
}
Cow c1;
priority_queue<Cow> pq;
int sel=1,ans=1;
void solve(){
pq.push(c[0]);
anl[c[0].co]=ans;
for (int i = 1; i < n; i += 1)
{
c1=pq.top();
if (c[i].l>c1.r)
{
anl[c[i].co]=anl[c1.co];
pq.pop();
pq.push(c[i]);
}else{
ans++;
anl[c[i].co]=ans;
pq.push(c[i]);
}
}
printf("%d\n",ans);
for (int i = 0; i < n; i += 1)
{
printf("%d\n",anl[i]);
}
}
int main()
{
//ios_base::sync_with_stdio(0);
#ifdef JIngwei_Xu
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
while (scanf("%d",&n)!=EOF)
{
for (int i = 0; i < n; i += 1)
{
scanf("%d%d",&c[i].l,&c[i].r);
c[i].co=i;
// pq.push(c[i]);
}
sort(c,c+n,cmp);
// for (int i = 0; i < n; i += 1)
// {
// cout<<c[i].co<<":"<<c[i].l<<","<<c[i].r<<endl;
// }
// while (!pq.empty())
// {
// cout<<pq.top().co<<":"<<pq.top().l<<","<<pq.top().r<<endl;
// pq.pop();
// }
solve();
}
return 0;
}
