1 条题解
-
0
题意分析
题目中给出了(N)头奶牛,每头奶牛都有唯一编号且范围在(1)到(N)。但它们没有按编号升序排队,FJ 记录的是每头奶牛前面编号比它小的奶牛数量(第一头奶牛前面没有奶牛,所以不记录)。我们的任务就是根据这些数量信息,还原出奶牛准确的排队顺序。这意味着我们要利用这些数量信息,反推出每头奶牛在队列中的位置和编号。
解题思路
我们可以从最后一头奶牛开始往前处理。因为最后一头奶牛的信息(前面编号比它小的奶牛数量)能直接确定它在最终队列中的位置。例如,如果最后一头奶牛前面有0头编号比它小的奶牛,那么它就是当前队列中编号最大的,应该放在队列的最后一个位置。 接着处理倒数第二头奶牛,根据它前面编号比它小的奶牛数量,将它插入到当前队列中合适的位置。比如,倒数第二头奶牛前面有1头编号比它小的奶牛,那就从队首开始数,找到第2个位置(因为前面有1个更小的,所以它是第2个)插入这头奶牛。
按照这样的方式,依次处理每一头奶牛,从后往前,根据它们前面编号比它小的奶牛数量,将其插入到已构建的队列中合适位置,最终得到的队列就是奶牛准确的排队顺序。
代码
#include <iostream> #include <cstdio> // 包含scanf和printf所需的头文件 #include <cstdlib> // 包含system所需的头文件 using namespace std; int main() { int n; scanf("%d", &n); int rank[n], num[n]; rank[0] = 0; num[0] = 1; for (int i = 1; i < n; i++) { scanf("%d", &rank[i]); num[i] = i + 1; } for (int i = n - 1; i >= 0; i--) { int j = 0, k = 0; while (num[j] == 10000) j++; while (k < rank[i]) { j++; if (num[j] != 10000) k++; } rank[i] = num[j]; num[j] = 10000; } for (int i = 0; i < n; i++) printf("%d\n", rank[i]); system("pause"); // 注意:此语句仅适用于Windows系统调试 return 0; } ``` ```
- 1
信息
- ID
- 1182
- 时间
- 1000ms
- 内存
- 64MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 1
- 上传者