https://codeforces.com/contest/1659

D. Reverse Sort Sum

 

题意：有一个长为 nn 的数组 AA，共操作 nn 轮，第 ii 轮操作对 AA 中前 ii 个元素排序，把这 nn 轮得到的 nn 个数组对应位置相加，得到数组 CC，先给定数组 CC，要求还原出数组 AA。

双指针

目的是找出 AA 中所有 00 的位置。

一个指针指向当前轮的第一个 11，另一个指针指向当前知道的最后一个 00。

现在移动指向 00 的那个指针，若下一个位置是 11，则得到的数组和上一轮相同，那么指向第一个 11 的指针所在位置上的元素和+1（因为它这一轮还是 11）；若下一个位置是 00，则指向第一个 11 的指针所在位置上的元素和从此以后不再增加（因为它以后将始终是 00），所以只要看指向第一个 11 的指针相比于初始状态增加了几，就能知道指向 00 的指针移动了几次后找到了下一个 00​。

为了比较指向第一个 11 的指针相比于初始状态增加了几，就要把所有历史轮次操作组成的矩阵填充成右上部分全1，左下部分全0。

找到了下一个 00 之后，更新两个指针：指向 11 的指针右移一位，指向 00 的指针指向已经知道的下一个 00。

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
#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e6 + 10;
typedef pair<int, int> pii;

int T;
int n;
int a[N], ans[N];

int main() {
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        a[0] = 0;
        for(int i = 1; i <= n; i++)scanf("%d", &a[i]);
        for(int i = 1; i <= n; i++)ans[i] = 1;
        int f = -1;
        for(int i = 1; i <= n; i++){
            if(a[i] > 0){
                f = i - 1;
                break;
            }
            ans[i] = 0;
        }
        a[f] += f - 1;
        for(int i = f + 1; i <= n; i++){
            f = f + a[i] - a[i - 1];
            if(f > n)break;
            ans[f] = 0;
            a[f] += f - 1;
        }
        for(int i = 1; i <= n; i++)printf("%d%c", ans[i], " \n"[i == n]);
    }
    return 0;
}