题解 P3903 【导弹拦截III】

Weng_Weijie · 2017-10-02 14:22:56 · 题解

本题与NOIP2013D2T2 花匠差不多， 可用贪心做

首先我们知道在一个递增(递减)序列中最多只能打两颗导弹

所以在一个任意的序列中，最多能打的数量就是峰点和谷点数量之和，这样才最优

(注意！！刚开始只能往下打，即若一开始是递增序列，则答案减一)

#include <stdio.h>
int flag = 0, now, last, n, ans = 1; //ans表示打下的导弹数
//flag表示当前是递增还是递减 0:递增 1:递减
//因为刚开始必须是递减，所以flag初值为0
int main() {
    scanf("%d%d", &n, &now);
    while (--n) {
        last = now;
        scanf("%d", &now);
        if (now == last) continue; //由于是严格的，所以相等直接退出
        if (flag ^ (now < last))  //如果递增(递减) 状态与当前不同那么答案加一（就是又找到了一个峰点(谷点)）
            ans++, flag = now < last;
    }
    printf("%d\n", ans);
    return 0;
}