自动搬运

查看原文

来自洛谷，原作者为

	Weng_Weijie やー！今日もパンがうまい！

搬运于2025-08-24 21:53:55，当前版本为作者最后更新于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;
}