Median

Posted on | In , , ,

题目链接

题意

有数列$a$，长度为$n$。
定义$M(a, b, c)$为$a,b,c$的中位数。
已知数列，还原$a$数列。

思路

首先要观察一个优美的结论如果不等于和它相关的三个中位数中的任意一个，那么它一定是三个相邻数字中最大的或最小的，且要么大于三个相关中位数，要么都小于它们。
好像也比较显然？
如果他不是三个数字中的最值，那么它一定有从三个数中排名变化的过程，中间必然会变成中位数。
那么我们让他强行等于中位数也是没问题的。
所以我们$a{i}$的备选项就只有$$b{i-2},b{i-1},b{i}$$。
dp过程见代码。

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define dep(i,j,k) for(int i=k;i>=j;i--)
#define INF 0x3f3f3f3f
#define mem(i,j) memset(i,j,sizeof(i))
#define make(i,j) make_pair(i,j)
#define pb push_back
#define Pi acos(-1.0)
using namespace std;
const int N = 1e5 + 5;
int n, a[N], dp[N][3][3], pre[N][3][3], G[N][3], ans[N];
/// 前提： 结论已搞懂
/// dp[i][j][k]表示前面的 i - 2未已经构造好了，第i个数选择它能选择的三个数中，第j大的
///然后第i - 1个数选择它能选的三个数中的第 k 大的，这个方案是否能满足前i个都满足
/// pre[i][j][k] 代表 dp[i][j][k] 的上一个状态，也就是 第 i - 2 个数选择的是它所能选择的第几大的数
/// G[i][j] 是与 i 这个位置有关系的三个数中， 第j小的
int Mid(int a, int b, int c) { /// 找第二大的
    if(a > b) swap(a, b);
    if(a > c) swap(a, c);
    if(b > c) swap(b, c);
    return b;
}
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        rep(i, 3, n) scanf("%d", &a[i]);
        a[2] = a[1] = a[3];
        a[n + 2] = a[n + 1] = a[n];
        rep(i, 1, n) rep(j, 0, 2) rep(k, 0, 2) dp[i][j][k] = 0, pre[i][j][k] = 0; /// 预处理
        G[1][0] = G[1][1] = G[1][2] = a[1];
        rep(i, 2, n) G[i][0] = a[i], G[i][1] = a[i + 1], G[i][2] = a[i + 2]; /// 预处理
        rep(i, 0, 2) rep(j, 0, 2) dp[2][i][j] = 1;
        rep(i, 3, n) rep(j, 0, 2) rep(k, 0, 2) rep(l, 0, 2) {///枚举前面一位（i - 1）的所有可行方案
            if(dp[i - 1][k][l]) { /// 找到前面一位(i - 1)的一个可行方案
                if(Mid(G[i - 2][l], G[i - 1][k], G[i][j]) == a[i]) { /// i 这个方案可行
                    pre[i][j][k] = l;
                    dp[i][j][k] = 1;
                    break;
                }
            }
        }
        bool flag = true;
        int fi, se;
        rep(i, 0, 2) {
            rep(j, 0, 2) {
                if(dp[n][i][j] == 1) { /// 找可行方案
                    fi = i;
                    se = j;
                    flag = false;
                    break;
                }
            }
            if(!flag) break;
        }
        if(flag) { /// 无解
            puts("-1"); continue;
        }
        ans[n] = G[n][fi]; ans[n - 1] = G[n - 1][se];
        dep(i, 1, n - 2) { /// 回溯找答案
            ans[i] = G[i][pre[i + 2][fi][se]];
            int tmp = fi;
            fi = se;
            se = pre[i + 2][tmp][se];
        }
        rep(i, 1, n) printf("%d ", ans[i]);
        puts("");
    }
    return 0;
}

0%