Article From:https://www.cnblogs.com/ppprseter/p/9060350.html

P1823 concert waiting

Title Description

\(N\)A person is lining up into a concert. People waited so bored that they began to turn around and try to find their acquaintances in the team. Any two people in the queue\(A\)and\(B\),If they are adjacent to or between them, no one is compared.\(A\)or\(B\)High, then they can see each other.

Write a program to figure out how many people can see each other.

input and output format

Input Format:

The first line of input contains an integer\(N (1 ≤ N ≤ 500 000)\), Express the ranks of the team\(N\)Individual.

Next\(N\)Each row contains an integer representing the height of the human being, in the case of nanometre.\(10^{-9}\)As a unit, the scheduling of each person is less than that of a unit.\(2^{31}\)Nanometre. These heights represent the height of the people in the team.

\(S\),Express the ranks of the team\(S\)People can see each other.


A very obvious monotonous stack.

Maintain a sequence that is not strictly decreasing, and add one shot at a time.\(ans\)You can.

There are two points:

  1. Treatment of people with equal height
    I used the extra CNT to record the number of occurrences of each height and the number of times when popping up.

However, we should pay attention to the fact that we must not add CNT when dealing with adjacent areas. At the very beginning, this is only 25 points.

2.open\(long\) \(long\)


code:

#include <cstdio>
#define ll long long
const ll N=500010;
ll a,ans=0,top=0,n;
struct node
{
    ll cnt,h;
}s[N];
void pop() {top--;}
void push(node t) {s[++top]=t;}
int main()
{
    scanf("%lld",&n);
    node t;
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&a);
        t.cnt=1;
        t.h=a;
        while(top&&s[top].h<=a)
        {
            if(s[top].h==a) t.cnt+=s[top].cnt;
            ans+=s[top].cnt;
            pop();
        }
        if(top) ans+=1;
        push(t);
    }
    printf("%lld\n",ans);
    return 0;
}

2018.5.19

Similar Posts:

Leave a Reply

Your email address will not be published. Required fields are marked *