首页 > 代码库 > P2866 糟糕的一天
P2866 糟糕的一天
糟糕的一天
洛谷链接
挺水的一道题,也就是看每个数后面有多少数比它小,最后把总数加起来。
我们可以用单调栈来实现,并用一个数组来保存每个数现在的状态。
代码:
1 #include<cstdio> 2 long long n,a[80010],stack[80010],top,ans=0; 3 int main(){ 4 scanf("%lld",&n); 5 for(long long i=1;i<=n;i++) 6 scanf("%lld",&a[i]); 7 a[n+1]=1<<30; 8 for(long long i=1;i<=n+1;i++){ 9 while(top&&a[stack[top]]<=a[i]){ 10 ans+=i-stack[top]-1; 11 top--; 12 } 13 stack[++top]=i; 14 } 15 printf("%lld",ans); 16 return 0; 17 }
P2866 糟糕的一天
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。