N个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。队列中任意两个人A和B，如果他们是相邻或他们之间没有人比A或B高，那么他们是可以互相看得见的。
写一个程序计算出有多少对人可以互相看见。
重点：
（1）看题要仔细
（2）不开long long 见祖宗
解法神奇
#include<cstdio> #include<cstdlib> #include<stack> #define ll long long using namespace std; int n; const int N=500003; int x,tt; ll ans; struct node { int v;ll sum; }d[N]; stack <node> s; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&x); if(x==d[tt].v ) d[tt].sum ++; else d[++tt].v =x,d[tt].sum =1; } for(int i=1;i<=tt;i++) { ll cnt=0,res=0; while(!s.empty() && s.top() .v < d[i].v ) //还是有可能在删除了一些结构体之后，还有相等的元素 cnt+=s.top().sum , s.pop() ; if(!s.empty() && s.top().v==d[i].v ) res =s.top().sum , s.pop() ; if(!s.empty() ) cnt+=d[i].sum ; ans+=cnt + res*d[i].sum + d[i].sum *(d[i].sum -1) /2 ; s.push((node){d[i].v ,res+d[i].sum }); } printf("%lld\n",ans); return 0; }
原文：https://www.cnblogs.com/xwww666666/p/11729048.html