Stall Reservations
| Time Limit: 1000MS | Memory Limit: 65536K | |||
| Total Submissions: 3106 | Accepted: 1117 | 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:
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, N
Lines 2..N+1: Line i+1 describes cow i's milking interval with two space-separated integers.
Lines 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.
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 7
Sample Output
4
1
2
3
2
4
Hint
Explanation of the sample:
Here's a graphical schedule for this output:
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.
Source
/*
** 用堆维护的贪心题。先依照開始时间排序。再将牛依次放入堆里。放入之前更新堆顶元素。
** TLE到吐。。。
*/ #include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue> #define maxn 50010
using namespace std; struct Node2 {
int num, u, v;
friend bool operator<(const Node2& a, const Node2& b) {
return a.v > b.v;
}
} cow[maxn];
int ans[maxn]; bool cmp(const Node2& a, const Node2& b) {
return a.u < b.u;
} int main() {
int N, i, j, sum, u, v, flag;
Node2 tmp;
while(scanf("%d", &N) == 1) {
sum = 0;
for(i = 0; i < N; ++i) {
scanf("%d%d", &u, &v);
cow[i].num = i + 1;
cow[i].u = u;
cow[i].v = v;
ans[i + 1] = 0;
}
sort(cow, cow + N, cmp); priority_queue<Node2> PQ;
PQ.push(cow[0]);
ans[cow[0].num] = ++sum; for(i = 1; i < N; ++i) {
tmp = PQ.top();
if(cow[i].u > tmp.v) {
tmp.v = cow[i].v;
ans[cow[i].num] = ans[tmp.num];
PQ.pop(); PQ.push(tmp);
} else {
ans[cow[i].num] = ++sum;
PQ.push(cow[i]);
}
} printf("%d\n", sum);
for(i = 1; i <= N; ++i)
printf("%d\n", ans[i]);
}
return 0;
}
超时代码1：
#include <stdio.h>
#include <string.h>
#include <algorithm> #define maxn 50010
using std::sort; struct Node {
int u, v;
} E[maxn];
struct Node2 {
int num, u, v;
} cow[maxn];
int ans[maxn]; bool cmp(const Node2& a, const Node2& b) {
return a.u < b.u;
} int main() {
int N, i, j, sum, u, v;
while(scanf("%d", &N) == 1) {
sum = 0;
for(i = 0; i < N; ++i) {
scanf("%d%d", &u, &v);
cow[i].num = i + 1;
cow[i].u = u;
cow[i].v = v;
}
sort(cow, cow + N, cmp); for(i = 0; i < N; ++i) {
E[i].v = 0;
for(j = 0; j <= i; ++j) {
if(cow[i].u > E[j].v) {
if(!E[j].v) ++sum;
E[j].v = cow[i].v;
E[j].u = cow[i].u;
ans[cow[i].num] = j + 1;
break;
}
}
} printf("%d\n", sum);
for(i = 1; i <= N; ++i)
printf("%d\n", ans[i]);
}
return 0;
}
超时代码2：
#include <stdio.h>
#include <string.h>
#include <algorithm> #define maxn 50010
using std::sort; struct Node {
int u, v;
} E[maxn];
struct Node2 {
int num, u, v;
} cow[maxn];
int ans[maxn]; bool cmp(const Node2& a, const Node2& b) {
return a.u < b.u;
} int main() {
int N, i, j, sum, u, v, flag;
while(scanf("%d", &N) == 1) {
sum = 0;
for(i = 0; i < N; ++i) {
scanf("%d%d", &u, &v);
cow[i].num = i + 1;
cow[i].u = u;
cow[i].v = v;
ans[i + 1] = 0;
}
sort(cow, cow + N, cmp); for(i = 0; i < N; ++i) {
if(ans[cow[i].num]) continue;
ans[cow[i].num] = ++sum;
flag = cow[i].v;
for(j = i + 1; j < N; ++j)
if(!ans[cow[j].num] && cow[j].u > flag) {
flag = cow[j].v;
ans[cow[j].num] = sum;
}
} printf("%d\n", sum);
for(i = 1; i <= N; ++i)
printf("%d\n", ans[i]);
}
return 0;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。