炼金术师

炼金术师

https://ac.nowcoder.com/acm/contest/11169/A

炼金术师

题目链接:nowcoder 217127

到主站看:https://blog.csdn.net/weixin_43346722/article/details/116243190

题目大意

给你一些操作,每次将 1~x 的地方染上一个新的颜色。
你可以任意选一个颜色,选一个 x 把 1~x 的地方都染上这个颜色。
问你你至少要染多少次才能染的跟题目的一样。

思路

根据题目容易看出它就是要你维护一个单调队列,然后问你到最后它的长度。

然后你就跟着做就好了。

代码

#include<cstdio>

using namespace std;

int n, x, q[1000001];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        while (q[0] && q[q[0]] <= x) q[0]--;
        q[++q[0]] = x;//维护单调队列
    }

    printf("%d", q[0]);//输出最后单调队列的长度

    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
06-05 04:14
已编辑
真烦好烦真烦:看着感觉好强啊,这都过不了吗
投递字节跳动等公司7个岗位 面试中的破防瞬间
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务