| 题目名称 | 3406. Lost cows |
|---|---|
| 输入输出 | lostcows.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 7 |
| 题目来源 |
 syzhaoss
于2020-05-26加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：8， 提交：8， 通过率：100% | ||||
 锝镆氪锂铽 |
100 | 0.000 s | 0.00 MiB | C++ |
|
yrtiop |
100 | 0.000 s | 0.00 MiB | C++ |
|
┭┮﹏┭┮ |
100 | 0.000 s | 0.00 MiB | C++ |
 数声风笛ovo |
100 | 0.000 s | 1.26 MiB | C++ |
|
syzhaoss |
100 | 0.035 s | 3.93 MiB | C++ |
 波风水门 |
100 | 0.057 s | 3.93 MiB | C++ |
 魔笛 |
100 | 0.189 s | 4.30 MiB | C++ |
 田三川 |
100 | 0.443 s | 8.29 MiB | C++ |
| 关于 Lost cows 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
二维数组倍增O(nlogn)
| ||||
【题目描述】
有$n$头奶牛，已知它们的身高为$1\sim n$且各不相同，但不知道每头奶牛的具体身高。
现在这$n$头奶牛站成一列，已知第$i$头牛前面有$a_i$头牛比它低，求每头奶牛的身高。
【输入格式】
第1行：输入整数n。
第2..n行：每行输入一个整数$a_i$,第$i$行表示第$i$头牛前面有$a_i$头牛比它低。
（注意：因为第1头牛前面没有牛，所以并没有将它列出）
【输出格式】
输出包含$n$行，每行输出一个整数表示牛的身高。
第$i$行输出第i头牛的身高。
【样例输入】
5 1 2 1 0
【样例输出】
2 4 5 3 1
【数据范围】
$1\leq n\leq 10^5$。
【来源】
《算法竞赛进阶指南》