Skip to content

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\) 则她们的身高满足:

math

\(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;
}