2019ACM-ICPC南京网络赛Greedy Sequence

喜欢ヅ旅行 2023-06-05 12:33 50阅读 0赞

**Greedy Sequence**

**限制**

5000 ms

256 MB

You're given a permutation a of length n (1 ≤ n ≤ 105).

For each i ∈ \[1, n\], construct a sequence si by the following rules:

1. si\[1\] = i;

2. The length of si is n, and for each j ∈ \[2, n\], si\[j\] ≤ si\[j − 1\];

3. First, we must choose all the possible elements of si from permutation a. If the index

of si\[j\] in permutation a is pos\[j\], for each j ≥ 2, ∣pos\[j\] − pos\[j − 1\]∣ ≤ k (

1 ≤ k ≤ 105). And for each si, every element of si must occur in a at most once.

4. After we choose all possible elements for si, if the length of si is smaller than n, the

value of every undetermined element of si is 0;

5. For each si, we must make its weight high enough.

Consider two sequences C = \[c1, c2, ...cn\] and D = \[d1, d2, ..., dn\], we say the weight

of C is higher than that of D if and only if there exists an integer k such that 1 ≤ k ≤ n,

ci = di for all 1 ≤ i < k, and ck > dk .

If for each i ∈ \[1, n\], ci = di, the weight of C is equal to the weight of D.

For each i ∈ \[1, n\], print the number of non-zero elements of si separated by a space.It's guaranteed that there is only one possible answer.

**Input**

There are multiple test cases.

The fifirst line contains one integer T(1 ≤ T ≤ 20), denoting the number of test cases.

Each test case contains two lines, the fifirst line contains two integers n and k (

1 ≤ n, k ≤ 105), the second line contains n distinct integers a1, a2, ..., an (1 ≤ ai ≤ n)

separated by a space, which is the permutation a.

**Output**

For each test case, print one line consists of n integers ∣s1∣, ∣s2∣, ..., ∣sn∣ separated by a

space.

∣si∣ is the number of non-zero elements of sequence si.

There is no space at the end of the line.

**Sample Input 1**

3 1

3 2 1

7 2

3 1 4 6 2 5 7

**Sample Output 1**

1 2 3

1 1 2 3 2 3 3

前面的ans对后面的ans有贡献，用 num \[ i \] 存 len ( S i )，然后找到满足条件的 a\[ j \] （即 abs（j - i）<=k ），len ( S i ) = 1 + num \[ a\[ j \] \]。

题目给的5000ms，1014ms就过了，嗨森。。（不过应该还可以更快，比赛的时候sb了，加了个memset。。。）

![1754589-20190902103515658-2141153458.png][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 const int maxn=1e6+7;
     4 struct NODE
     5 {
     6     int data;
     7     int id;
     8 }node[maxn];
     9 bool cmp(NODE a,NODE b)
    10 {
    11     return a.data<b.data;
    12 }
    13 int num[maxn];
    14 int main()
    15 {
    16     int t;
    17     scanf("%d",&t);
    18     while(t--)
    19     {
    20         int n,k;
    21         scanf("%d%d",&n,&k);
    22         for(int i=1;i<=n;++i)
    23         {
    24             scanf("%d",&node[i].data);
    25             node[i].id=i;
    26         }
    27         sort(node+1,node+n+1,cmp);
    28         //memset(num,0,sizeof(num));
    29         for(int i=1;i<=n;++i)
    30         {
    31             int len=1;
    32             int pos=node[i].id;
    33             for(int j=i-1;j>=1;--j)
    34             {
    35                 if(abs(pos-node[j].id)<=k)
    36                 {
    37                     len+=num[j];
    38                     break;
    39                 }
    40             }
    41             num[i]=len;
    42             printf("%d",len);
    43             if(i<n)printf(" ");
    44             else printf("\n");
    45         }
    46     }
    47     return 0;
    48 }

转载于:https://www.cnblogs.com/CharlieWade/p/11443368.html

[1754589-20190902103515658-2141153458.png]: /images/20230601/e122e159807f4ac09a61b695b4fb85d9.png