Codeforces 319B. Psychos in a Line【栈】

题目大意:

一串数列,每一个值如果大于相邻右一位的值的话,那么就可以把右边这个值“吃掉”(右一位消失,原来的值不变),问需要吃多少次才能到达无法再吃的状态。

做法:

利用栈。遍历一遍数组,处理每个值的时候,如果栈顶的元素小于该值,那么将其弹出,知道栈顶元素大于该值或者栈为空,栈内的每个元素记录下一个属性:他是在第几次被“吃掉”,进栈的新元素的被吃次数就是它弹出去的元素中的属性的最大值+1,如果没有弹任何值则为1;如果栈空,则值为0;

代码:

#include <iostream>
#include <cstdio>
#define N 100010
using namespace std;
int a[N];
int ans,n;
struct aa
{
    int x,eat;
}que[N];
int main()
{
    int tail=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",a+i);
    int i=1;
    while(a[i-1]<a[i] && i<n) i++;
    que[tail].x=a[i-1],que[tail++].eat=0;
    for(;i<n;i++)
    {
        if(a[i]<que[tail-1].x)
        {
            que[tail].x=a[i],que[tail++].eat=1;
            ans=max(ans,que[tail-1].eat);
            continue;
        }
        int ma=0;
        while(tail>0 && a[i]>que[tail-1].x) ma=max(ma,que[tail-1].eat),tail--;
        if(tail==0) que[tail].eat=0;
        else que[tail].eat=ma+1;
        que[tail++].x=a[i];
        ans=max(ans,que[tail-1].eat);
    }

    cout<<ans<<endl;
    return 0;
}
时间: 08-28

Codeforces 319B. Psychos in a Line【栈】的相关文章

Codeforces 319B. Psychos in a Line【单调栈】

题目链接: http://codeforces.com/problemset/problem/319/B 题意: 一串数列,每一个值如果大于相邻右一位的值的话,那么就可以把右边这个值"吃掉"(右一位消失,原来的值不变),问需要吃多少次才能到达无法再吃的状态. 思路: 利用栈.遍历一遍数组,处理每个值的时候,如果栈顶的元素小于该值,那么将其弹出,知道栈顶元素大于该值或者栈为空,栈内的每个元素记录下一个属性:他是在第几次被"吃掉",进栈的新元素的被吃次数就是它弹出去的元

CF 319B Psychos in a Line 【单调队列】

给出一排神经病的编号1-n的某个排列 给出规则 一步能同时消除该数右边连续的小于该数的数 问几步能消到最后状态 在纸上试了试,觉得这个问题很有点像lis,但是苦于方法 突然看了一眼tags 单调队列 oh it is 可以把这些数字一个一个的加入单调队列中 同时记录每个数字被吃掉的场次 保持整个队列递减 策略如下 如果一个数进去没有弹出数,则这个数肯定是第一场就被消掉的 如果一个数进去弹出了一些数,则该数被吃掉的场次等于它弹走的所有数中最大的被吃掉的场次序号+1 因为,这个数肯定是在它弹掉的数之

Codeforces Round #189 (Div. 1) B. Psychos in a Line 单调队列

B. Psychos in a Line Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/problemset/problem/319/B Description There are n psychos standing in a line. Each psycho is assigned a unique integer from 1 to n. At each step every psycho who h

Psychos in a Line

Psychos in a Line TimeLimit:1000MS  MemoryLimit:256MB 64-bit integer IO format:%I64d Problem Description There are n psychos standing in a line. Each psycho is assigned a unique integer from 1 to n. At each step every psycho who has an id greater tha

Codeforces 344D Alternating Current 简单使用栈

Description Mad scientist Mike has just finished constructing a new device to search for extraterrestrial intelligence! He was in such a hurry to launch it for the first time that he plugged in the power wires without giving it a proper glance and st

Codeforces 547B Mike and Feet(单调栈)

题目链接:http://codeforces.com/problemset/problem/547/B 题目大意:有一个长度为n的序列,序列有长度为1...n的连续子序列,一个连续子序列里面最小的值称作这个子序列的子序列的strength,要求出每种长度的连续子序列的最大的strength.解题思路:可以用栈求出每个点的l[i],表示值小于当前位置并且在左侧的最接近这个点的位置.同理可以求出r[i],表示值小于当前位置并且在右侧侧的最接近这个点的位置.求l[i]过程如下:stack s // i

Codeforces 516D Drazil and Morning Exercise (栈、二分)

题目链接 https://codeforces.com/contest/516/problem/D 题解 我还是数据结构水平太低了啊--连一个点子树内距离不超过\(l\)的点数都不会求 首先有一个熟知的结论是,我们任取原树的一条直径,那么对于任何一个点,直径的两端点中至少有一个到它的距离等于它到所有点的最远距离. 假设直径是\((u_d,v_d)\), 那么我们就把\(u\)的最远距离的式子化简成了\(f_u=\max(dis(u,u_d),dis(u,v_d)\). 考虑\(u_d\)和\(v

Codeforces Beta Round #7 C. Line (扩展欧几里德)

题目链接:http://codeforces.com/problemset/problem/7/C 给你一个直线方程,有整数解输出答案,否则输出-1. 扩欧模版题.这里有讲解:http://www.cnblogs.com/Recoder/p/5459812.html (很久没写exgcd,都不会写了) 1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 5 LL exgcd(LL a , LL

Codeforces 547B. Mike and Feet[单调栈/队列]

这道题用单调递增的单调栈维护每个数能够覆盖的最大区间即可. 对于   1 2 3 4 5 4 3 2 1 6 这组样例, 1能够覆盖的最大区间是10,2能够覆盖的最大区间是7,以此类推,我们可以使用单调栈来实现这种操作. 具体看代码: *Code: #include<bits/stdc++.h> using namespace std; int n,l[200005],r[200005],ans[200005],a[200005]; int stk[200005],top=0; void so