HDU 6040 Hints of sd0061 （技巧）

HDU 6040 Hints of sd0061 （技巧）

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 ai. sd0061 prepares one hint for each contest. The hint for the j-th contest is a number bj, which means that the noob with the (bj+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: bi+bj≤bk is satisfied if bi≠bj, bi

Input

There are multiple test cases (about 10).For each test case:The first line contains five integers n,m,A,B,C. (1≤n≤10^7,1≤m≤100)The second line contains m integers, the i-th of which is the number bi of the i-th hint. (0≤bi

Output

For each test case, output “Case #x: y1 y2 ⋯ ym” in one line (without quotes), where x indicates the case number starting from 1 and yi (1≤i≤m) denotes the rating of noob for the i-th contest of corresponding case.

Sample Input

3 3 1 1 10 1 22 2 2 2 21 1

Sample Output

Case #1: 1 1 202755Case #2: 405510 405510

题意

用题中所给的函数生成 n 个数，然后有 m 次查询，查询数列 a 中第 bi

思路

如果单纯想着排序以后直接输出的话会超时，因为 n 最大有 107

那么就应该想想其他线性的解法了， STL 库中实现了 ​​nth_element​​ 函数，其功能是使第 n 大元素处于第 n 个位置，并且比这个元素小的元素都排在它之前，比这个元素大的元素都排在它之后，但不能保证它们是有序的。

template void

时间复杂度：平均为线性。

然后在使用过程中做一点点的优化就可以了，题中有说 bi+bj≤bk

AC 代码

#include#include#include#include#includeusing namespace std;unsigned x, y, z;unsigned rng61(){ unsigned t; x ^= x << 16; x ^= x >> 5; x ^= x << 1; t = x; x = y; y = z; z = t ^ x ^ y; return z;}typedef pair P;const int manx = 1e7+10;unsigned a[manx];unsigned ans[manx];P b[110];int main(){ ios::sync_with_stdio(false); int n,m,kase=0; while(cin>>n>>m>>x>>y>>z) { for(int i=0; i>b[i].first; b[i].second=i; } for(int i=0; i=0; i--) { nth_element(a,a+b[i].first,a+b[i+1].first); ans[b[i].second]=a[b[i].first]; } cout<<"Case #"<<++kase<<":"; for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。