1 条题解

  • 0
    @ 2025-5-22 10:27:12

    题意分析

    题目中给出了(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
    上传者