Problem 4076 --最长上升子序列

4076: 最长上升子序列

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $1$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

你原本有一个 1 到 n 的排列,但是不慎地,你遗忘了它,但是你记得以 第i个位置 结尾的最长上升子序列的长度数组 {an} ,现在希望你能够构造一个符合条件的排列 p ,如果不存在符合上述条件的排列 p ,则输出  - 1。

这里定义以 第i位置 结尾的最长上升子序列的长度,为符合以下条件的整数数组  中 k 的最大值。

本题输入输出量比较大,请选手注意。

第一行一个整数 n (1 ≤ n ≤ 106)

第二行 n 个整数表示数组 {an} (1 ≤ ain),其中 ai 表示以 i 结尾的最长上升子序列的长度。

一行 n 个整数表示排列 p ,如果无解,则输出  - 1
5
1 2 2 3 3
1 5 2 4 3 

推荐代码 查看4076 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战 AOJ大管家 1091830 2024-04-07 13:51:31

赛题来源/所属竞赛 2023年中国大学生程序设计竞赛女生专场 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛