Skip to content

11062: 【原1062】小M爱机器人队形

题目

题目描述

author: drf 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1062

Description

大家都知道,小M有N个机器人。PPCA水平测试之后,小M心血来潮,让N个机器人站成一排唱机器人之歌。小M要请其中的(N-K)只机器人出列,使得剩下的K个机器人排成机器人队形。(冷死人不偿命-.+)

机器人队形是指这样的一种队形:设K只机器人从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK, 则他们的身高满足\( T1 < ... < Ti > Ti+1 > … > TK (1 \leq i \leq K) \)。

因为机器人很卡哇伊O(∩_∩)O~,小M想让尽量少的机器人出列,使得剩下的机器人排成机器人队形。现在把N只机器人的告诉你,聪明的你,能帮帮小M吗?

Input Format

第一行是一个整数N( \( 2 \leq N \leq 1000000 \) ),表示机器人的总数。第一行有n个整数,用空格分隔,第i个整数Ti(\(0 \leq Ti \leq 10000000 \) )是第i只机器人的高度(纳米)。

Output Format

输出包括一行,这一行只包含一个整数,就是最少需要几只机器人出列。

说明

对于30分的数据,保证有\( n \leq 100 \) ;

对于全部的数据,保证有\( n \leq 1000000 \)。

改编自NOIP2004。

Sample Input

8
186 186 150 200 160 130 197 220

Sample Output

4

FineArtz's solution

/* 小M爱机器人队形 */
#include <iostream>
using namespace std;

int a[1000005], n;
int ans1[1000005], ans2[1000005], t[1000005];
int len;

int bisearch(int i){
    int l = 1, r = len, mid;
    while (l < r){
        mid = (l + r) / 2;
        if (t[mid] >= a[i])
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        ans1[i] = 1;
        ans2[i] = 1;
    }
    t[1] = a[1];
    len = 1;
    for (int i = 2; i <= n; ++i){
        if (a[i] > t[len]){
            t[++len] = a[i];
        }
        else{
            int p = bisearch(i);
            t[p] = a[i];
        }
        ans1[i] = len;
    }
    len = 1;
    t[1] = a[n];
    for (int i = n - 1; i >= 1; --i){
        if (a[i] > t[len]){
            t[++len] = a[i];
        }
        else{
            int p = bisearch(i);
            t[p] = a[i];
        }
        ans2[i] = len;
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = max(ans, ans1[i] + ans2[i] - 1);
    cout << n - ans << endl;
    return 0;
}

yyong119's solution

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int up = 1000001;
int a1[up], a2[up], f1[up], f2[up], g[up];

int main()
{
    int n, k, maxn = 0;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a1[i]);
        a2[n - i + 1] = a1[i];
    }
    memset(g, 0x7f, sizeof(g));
    for(int i = 1; i <= n; i++)
    {
        k = lower_bound(g + 1, g + n + 1, a1[i]) - g;
        f1[i] = k;
        g[k] = a1[i];
    }
    memset(g, 0x7f, sizeof(g));
    for(int i = 1; i <= n; i++)
    {
        k = lower_bound(g + 1, g + n + 1, a2[i]) - g;
        f2[n - i + 1] = k;
        g[k] = a2[i];
    }
    for(int i = 1; i <= n; i++) maxn = max(maxn, f1[i] + f2[i]);
    printf("%d\n", n + 1 - maxn);
}