13029: 【原3029】运动会

题目

题目描述

author: 李霖 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3029

Description

上海西南某高校运动会开幕了！

光体，沸腾了……

忽如一夜春风来，交大女生连成排！君不见，交大女生天上来，奔流到海不复回！只见数千女生穿着白裙，挥舞着红旗，舞出了天边最美的云彩！

表演当中，女生们不断变换着队形，赢得了观众的阵阵喝彩。假如现在我交有 \(N\) 个女生站成了一排，我们想要 \(N - K\) 个女生出列，使得剩下的 \(K\) 个女生形成这样的队形：

设 \(K\) 个女生从左到右依次编号为：\(1, 2, … , K\), 她们的身高分别为：\(H_1, H_2 , …, H_K\) 则她们的身高满足：

\(H_1 < ... < H_i > H_{i+1} > ... > H_K, 1\le i\le K\)

现在我们已经知道了这 \(N\) 个女生的身高，你的任务是算出最少要多少个女生出列，才能使剩下的女生站成我们想要的队形。

Input Format

第 \(1\) 行：一个整数\(N\) 表示一共有 \(N\) 个女生。

第 \(2\) 行到第 \(N + 1\) 行：每行一个整数，第 \(i + 1\) 行的整数表示第 \(i\) 个女生的身高\(H_i\)

Output Format

输出包括一行，这一行只包含一个整数，表示最少需要几个女生出列。

Hint

对于 \(30\) 分的数据，保证有：\(N \leq 20\)

对于 \(60\) 分的数据，保证有：\(N \leq 1500\)

对于 \(100\) 分的数据，保证有：\(N \leq 1000000\)

对于每个女生的身高\(H\) 我们有：\(140 \leq H \leq 220\)

Sample Input

5 
165 
172 
145 
162 
159

Sample Output

1

yyong119's solution

#include <iostream>
#include <cstdio>
#define MAX_N 1000010
#define max(x, y) ((x) > (y) ? (x) : (y))
using namespace std;
int n, len, ans;
int a[MAX_N], l[MAX_N], r[MAX_N], que[MAX_N];
inline int read() {
    char ch = getchar(); int res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    // if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    // return res * flag;
    return res;
}
int main() {
    n = read();
    for (register int i = 0; i < n; ++i) a[i] = read();
    // calc left
    len = 1; que[0] = a[0];
    for (register int i = 1; i < n; ++i) {
        int tmp = lower_bound(que, que + len, a[i]) - que;
        l[i] = tmp;
        if (tmp == len) que[len++] = a[i];
        else que[tmp] = a[i];
    }
    // calc right
    len = 1; que[0] = a[n - 1];
    for (register int i = n - 2; i >= 0; --i) {
        int tmp = lower_bound(que, que + len, a[i]) - que;
        r[i] = tmp;
        if (tmp == len) que[len++] = a[i];
        else que[tmp] = a[i];
    }
    // calc maximum
    ans = 0;
    for (register int i = 0; i < n; ++i)
        ans = max(ans, l[i] + r[i] + 1);
    printf("%d", n - ans);
    return 0;
}