Skip to content

11588: 【原1588】导弹拦截

题目

题目描述

author: DarkFlameMaster 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1588

Description

某国为了防御敌国的导弹袭击，发展中一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于等于前一发的高度。某天，雷达捕捉到敌国导弹来袭。如果只有一套这样的系统，最多能拦截多少枚导弹？如果要拦截所有导弹，最少需要多少套这样的拦截系统？

Input Format

第一行有一个整数N ，代表来袭导弹的数目。

接下来一行 N 个数分别代表每发导弹的高度 {X_1,X_2,…,X_N}。

Output Format

两行，分别是单系统最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数。

Sample Input

8
389 207 155 300 299 170 158 65

Sample Output

6
2

Limits

  • 对于100%的数据，1 <= x[i] <= 2^31 - 1

  • 对于30%的数据，n <= 100

  • 对于60%的数据，n <= 1000
  • 对于90%的数据，n <= 10000
  • 对于100%的数据，n <= 1000000

yyong119's solution 

#include <cstdio>
#include <cstring>
#define MAX_N 1000000
using namespace std;

int a[MAX_N + 1], m[MAX_N + 1];

int bs(int maxlen, int tmp) {

    int l = 1, r = maxlen;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (m[mid] == tmp) return mid;
        if (m[mid] > tmp) l = mid + 1;
        else r = mid - 1;
    }
    return l;

}

int bs2(int maxlen, int tmp) {

    int l = 1, r = maxlen;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (m[mid] == tmp) return mid;
        if (m[mid] < tmp) l = mid + 1;
        else r = mid - 1;
    }
    return l;

}

int main() {

    int n, maxlen, num = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);

    maxlen = 1; m[maxlen] = a[1];
    for (int i = 2; i <= n; ++i)
        if (a[i] <= m[maxlen]) {
            m[++maxlen] = a[i];
        }
        else {
            int p = bs(maxlen, a[i]);
            m[p] = a[i];
        }
    printf("%d\n", maxlen);

    memset(m, 0, sizeof(m));
    maxlen = 1; m[maxlen] = a[1];
    for (int i = 2; i <= n; ++i)
        if (a[i] > m[maxlen]) {
            m[++maxlen] = a[i];
        }
        else {
            int p = bs2(maxlen, a[i]);
            m[p] = a[i];
        }
    printf("%d\n", maxlen);
    return 0;
}