P3165 [CQOI2014]排序机械臂

    • 233通过
    • 449提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 Splay Treap 2014 重庆 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    为了把工厂中高低不等的物品按从低到高排好序,工程师发明了一种排序机械臂。它遵循一个简单的排序规则,第一次操作找到摄低的物品的位置P1,并把左起第一个至P1间的物品反序;第二次找到第二低的物品的位置P2,并把左起第二个至P2间的物品反序...最终所有的物品都会被排好序。

    上图给出_个示例,第_次操作前,菝低的物品在位置4,于是把第1至4的物品反序;第二次操作前,第二低的物品在位罝6,于是把第2至6的物品反序...

    你的任务便是编写一个程序,确定一个操作序列,即每次操作前第i低的物品所在位置Pi,以便机械臂工作。需要注意的是,如果有高度相同的物品,必须保证排序后它们的相对位置关系与初始时相同。

    输入输出格式

    输入格式:

    第一行包含正整数n,表示需要排序的物品数星。

    第二行包含n个空格分隔的整数ai,表示每个物品的高度。

    输出格式:

    输出一行包含n个空格分隔的整数Pi。

    输入输出样例

    输入样例#1: 复制
    6
    3 4 5 1 6 2
    输出样例#1: 复制
    4 6 4 5 6 6

    说明

    N<=100000

    Pi<=10^7

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。