当前位置：网站首页>HDU 6040 Hints of sd0061 （技巧）

HDU 6040 Hints of sd0061 （技巧）

2022-08-10 11:04:00 【51CTO】

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

Sample Output

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

题意

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

思路

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

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

       
       template
       
       <
       
       class 
       
       RandomAccessIterator
       
       >  
       
       void
      
1.
2.

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

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

AC 代码

       
       #include<iostream>
       
       #include<vector>
       
       #include<cstring>
       
       #include<algorithm>
       
       #include<cstdio>
       
       using 
       
       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
       
       <
       
       int,
       
       int
       
       > 
       
       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
       
       <
       
       m; 
       
       i
       
       ++)
       
        {
       
       cin
       
       >>
       
       b[
       
       i].
       
       first;
       
       b[
       
       i].
       
       second
       
       =
       
       i;
       
        }
       
       for(
       
       int 
       
       i
       
       =
       
       0; 
       
       i
       
       <
       
       n; 
       
       i
       
       ++)
       
       a[
       
       i]
       
       =
       
       rng61();
       
       sort(
       
       b,
       
       b
       
       +
       
       m);
       
       b[
       
       m].
       
       first
       
       =
       
       n;
       
       for(
       
       int 
       
       i
       
       =
       
       m
       
       -
       
       1; 
       
       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
       
       <
       
       m; 
       
       i
       
       ++)
       
       cout
       
       <<
       
       " "
       
       <<
       
       ans[
       
       i];
       
       cout
       
       <<
       
       endl;
       
    }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.