UVA501 Black Box

    • 19通过
    • 123提交
  • 题目来源 UVA 501
  • 评测方式 RemoteJudge
  • 标签
  • 难度 提高+/省选-
  • 时空限制 3000ms / 0MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    Description 我们使用黑匣子的一个简单模型。它能存放一个整数序列和一个特别的变量i。在初始时刻,黑匣子为空且i等于0。这个黑匣子能执行一系列的命令。有两类命令: ADD(x):把元素x放入黑匣子; GET:把i加1的同时,输出黑匣子内所有整数中第i小的数。牢记第i小的数是当黑匣子中的元素已非降序排序后位于第i位的元素。 下面是一个11个命令的例子: 编号 命令 i 黑匣子内容 输出 1 ADD(3) 0 3
    2 GET 1 3 3 3 ADD(1) 1 1,3
    4 GET 2 1,3 3 5 ADD(-4) 2 -4,1,3
    6 ADD(2) 2 -4,1,2,3
    7 ADD(8) 2 -4,1,2,3,8
    8 ADD(-1000) 2 -1000,-4,1,2,3,8
    9 GET 3 -1000,-4,1,2,3,8 1 10 GET 4 -1000,-4,1,2,3,8 2 11 ADD(2) 4 -1000,-4,1,2,2,3,8
    现需要一个有效的算法处理给定的一系列命令。ADD和GET命令的总数至多个有30000个。 定义ADD命令的个数为M个,GET命令的个数为N个。 我们用下面得两个整数序列描述命令序列: 1.A(1),A(2),……,A(M):加入黑匣子的元素序列。所有的数均为绝对值不超过2000000的整数。例如在上例中A=(3,1,-4,2,8,-1000,2)。 2.u(1),u(2),……,u(N):u(i)表示第i个GET命令在第u(i)个ADD命令之后,例如在上例中,u=(1,2,6,6)。 你可以假定自然数序列u(1),u(2),……,u(N)以非降序排列,N≤M,且对于每一个p(1≤p≤N)有p≤u(p)≤M 现在要求找出对于给定的命令串的最好的处理方法。ADD 和 GET 命令分别最多有30000个。 现在用两个整数数组来表示命令串:

    1. A(1), A(2), ..., A(M): 一串将要被放进Black Box的元素。每个数都是绝对值不超过2 000 000 000 的整数 M <= 30000。例如上面的例子就是A=(3, 1, -4, 2, 8, -1000, 2).
    2. u(1), u(2), ..., u(N): 表示第u(j)个元素被放进了Black Box里后就出现一个GET命令。例如上面的例子中u=(1, 2, 6, 6). 输入数据不用判错。 Input 题目有多组输入数据! 第一行是一个表示输入组数的整数 N ,隔一空行之后是 N 组输入数据,每组输入数据之间都有一行空行隔开,各组数据都是按上面的形式输入。 Output 输出包含 N 组输出数据,每一组之间用一个空行隔开。

    题目描述

    PDF

    输入输出格式

    输入格式:

    输出格式:

    输入输出样例

    输入样例#1: 复制
    1
    7 4
    3 1 -4 2 8 -1000 2
    1 2 6 6
    输出样例#1: 复制
    3
    3
    1
    2
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。