HDU6040 Hints of sd0061 分治排序

http://acm.hdu.edu.cn/showproblem.php?pid=6040

Hints of sd0061

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description

sd0061, the legend of Beihang University ACM-ICPC Team, retired last year leaving a group of noobs. Noobs have no idea how to deal with $m$ coming contests. sd0061 has left a set of hints for them.
There are $n$ noobs in the team, the $i$-th of which has a rating $a_i$. sd0061 prepares one hint for each contest. The hint for the $j$-th contest is a number $b_j$, which means that the noob with the $(b_j + 1)$-th lowest rating is ordained by sd0061 for the $j$-th contest.
The coach asks constroy to make a list of contestants. constroy looks into these hints and finds out: $b_i + b_j \leq b_k$ is satisfied if $b_i \neq b_j,$ $b_i < b_k$ and $b_j < b_k$.
Now, you are in charge of making the list for constroy.

Input

There are multiple test cases (about $10$).
For each test case:
The first line contains five integers $n, m, A, B, C$. $(1 \leq n \leq 10^7, 1 \leq m \leq 100)$
The second line contains $m$ integers, the $i$-th of which is the number $b_i$ of the $i$-th hint. $(0 \leq b_i < n)$
The $n$ noobs' ratings are obtained by calling following function $n$ times, the $i$-th result of which is $a_i$.

Output

For each test case, output "Case #$x$: $y_1$ $y_2$ $\cdots$ $y_m$" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y_i$ $(1 \leq i \leq m)$ denotes the rating of noob for the $i$-th contest of corresponding case.

Sample Input

Sample Output

Source

题意

给一个随机程序,生成一个长度为n的数组$a_i$,再给m次寻问$b_i$,询问数组$a_i$排序后,排名为$b_i+1$的数是多少。

思路

将询问的$b_i$数组排序,对$a_i$数组进行分治,类似于快排,选取参考点,交换数据后,在$b_i$数组中二分查找mid的范围,那么此时$b_i=mid$的询问都做出来了,此时$a_i$$b_i$数组都分成了左右两部分,直接递归处理这两部分即可。

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注