1017 The Best Peak Shape

Statement

Metadata

作者: CHEN, Yue
单位: 浙江大学
代码长度限制: 16 KB
时间限制: 2000 ms
内存限制: 64 MB

In many research areas, one important target of analyzing data is to find the best "peak shape" out of a huge amount of raw data full of noises. A "peak shape" of length $L$ is an ordered sequence of $L$ numbers { $D_1$ , $\cdots$ , $D_L$ } satisfying that there exists an index $i$ ( $1 < i < L$ ) such that $D_1 < \cdots < D_{i-1} < D_i > D_{i+1} > \cdots > D_L$ .

Now given $N$ input numbers ordered by their indices, you may remove some of them to keep the rest of the numbers in a peak shape. The best peak shape is the longest sub-sequence that forms a peak shape. If there is a tie, then the most symmetric (meaning that the difference of the lengths of the increasing and the decreasing sub-sequences is minimized) one will be chosen.

Input Specification

Each input file contains one test case. For each case, the first line gives an integer $N$ ( $3 \le N \le 10^4$ ). Then $N$ integers are given in the next line, separated by spaces. All the integers are in $[-10000, 10000]$ .

Output Specification

For each case, print in a line the length of the best peak shape, the index (starts from 1) and the value of the peak number. If the solution does not exist, simply print "No peak shape" in a line. The judge's input guarantees the uniqueness of the output.

Sample Input1

20
1 3 0 8 5 -2 29 20 20 4 10 4 7 25 18 6 17 16 2 -1

Sample Output1

10 14 25

Sample Input2

5
-1 3 8 10 20

Sample Output2

No peak shape

Solution

C++

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10;
int n, a[N], f[N], g[N];

struct Hash {
    vector<int> a;
    int& operator[](int x) {
        return a[x - 1];
    }
    int size() {
        return a.size();
    }
    void init() {
        a.clear();
    }
    void add(int x) {
        a.push_back(x);
    }
    void gao() {
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());
    }
    int get(int x) {
        return lower_bound(a.begin(), a.end(), x) - a.begin() + 1;
    }
} hs;

struct BIT {
    int a[N];
    void init() {
        memset(a, 0, sizeof a);
    }
    void update(int x, int v) {
        for (; x < N; x += x & -x) a[x] = max(a[x], v);
    }
    int query(int x) {
        if (x < 0)
            return 0;
        int res = 0;
        for (; x; x -= x & -x) res = max(res, a[x]);
        return res;
    }
} bit;

void gao(int* f) {
    bit.init();
    for (int i = 1; i <= n; ++i) {
        f[i] = 1 + bit.query(a[i] - 1);
        bit.update(a[i], f[i]);
    }
}

int main() {
    scanf("%d", &n);
    hs.init();
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), hs.add(a[i]);
    hs.gao();
    for (int i = 1; i <= n; ++i) a[i] = hs.get(a[i]);
    gao(f);
    reverse(a + 1, a + 1 + n);
    gao(g);
    reverse(a + 1, a + 1 + n);
    reverse(g + 1, g + 1 + n);
    int maxLen = -1, pos = -1, dif = 0;
    for (int i = 2; i < n; ++i) {
        if (f[i] > 1 && g[i] > 1) {
            if ((f[i] + g[i] - 1 > maxLen) || (f[i] + g[i] - 1 == maxLen && abs(f[i] - g[i]) < dif)) {
                maxLen = f[i] + g[i] - 1;
                dif = abs(f[i] - g[i]);
                pos = i;
            }
        }
    }
    if (maxLen == -1)
        puts("No peak shape");
    else
        printf("%d %d %d\n", maxLen, pos, hs[a[pos]]);
    return 0;
}

Last update: May 4, 2022