| 题目名称 | 3448. 畜栏预定 |
|---|---|
| 输入输出 | stallreservation.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 syzhaoss
于2020-08-10加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：13， 提交：36， 通过率：36.11% | ||||
 syzhaoss |
100 | 0.022 s | 2.88 MiB | C++ |
|
锝镆氪锂铽 |
100 | 0.022 s | 2.88 MiB | C++ |
|
yrtiop |
100 | 0.026 s | 0.81 MiB | C++ |
|
op_组撒头屯 |
100 | 0.033 s | 1.22 MiB | C++ |
|
┭┮﹏┭┮ |
100 | 0.036 s | 0.00 MiB | C++ |
|
Nj_L |
100 | 0.093 s | 3.54 MiB | C++ |
|
湖岸与夜与咸鱼 |
100 | 0.231 s | 0.00 MiB | C++ |
|
Nj_L |
100 | 0.289 s | 3.58 MiB | C++ |
|
元始天尊 |
100 | 0.336 s | 3.57 MiB | C++ |
|
黄天乐 |
100 | 0.346 s | 3.56 MiB | C++ |
| 关于 畜栏预定 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
很像廊桥分配
┭┮﹏┭┮
2022-08-21 17:48
3楼
| ||||
|
1
┭┮﹏┭┮
2022-08-21 17:46
2楼
| ||||
|
注意两个牛交集不可以被分到一个畜栏
┭┮﹏┭┮
2022-08-21 17:46
1楼
| ||||
【题目描述】
有N头牛在畜栏中吃草。
每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。
给定N头牛和每头牛开始吃草的时间A以及结束吃草的时间B，每头牛在[A,B]这一时间段内都会一直吃草。
当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。
求需要的最小畜栏数目和每头牛对应的畜栏方案。
【输入格式】
第1行：输入一个整数N。
第2..N+1行：第i+1行输入第i头牛的开始吃草时间A以及结束吃草时间B，数之间用空格隔开。
【输出格式】
第1行：输入一个整数，代表所需最小畜栏数。
第2..N+1行：第i+1行输入第i头牛被安排到的畜栏编号，编号是从1开始的 连续 整数，只要方案合法即可。
【样例输入】
5 1 10 2 4 3 6 5 8 4 7
【样例输出】
4 1 2 3 2 4
【数据范围】
$1≤N≤50000,1≤A,B≤1000000$。
【来源】
《算法竞赛进阶指南》