BZOJ1113: [Poi2008]海报PLA

• 单调栈扫一遍就是了，给出的矩形的长没有什么用，只看矩形的宽，出栈的时候ans++，最后统计栈里元素个数，加到ans里
• 注意的地方：当栈里最大元素跟当前相同时不进栈也不加ans
• 代码：
  

  #include <bits/stdc++.h>
  #define nmax 250010
   
  using namespace std;
  typedef long long ll;
  int n,idx=0;
  ll ans=0;
  ll s[nmax]; //单调递增的栈
   
  int main(){
      cin>>n;
      ll a,b;
      scanf("%lld%lld",&a,&b);
      s[0]=b;
      for (int i=1; i<n; i++) {
          scanf("%lld%lld",&a,&b);
          //把b入栈
           while(s[idx]>b){ ans++; idx--; }
          if(s[idx]!=b) s[++idx]=b;
      }
      //统计栈内不同的元素个数
      for (int i=idx; i>0; i--){
          if(s[i]!=s[i-1]) ans++;
      }
      ans++;
      cout<<ans<<endl;
      return 0;
  }    

  ヽ(??▽?)ノ

   

菜需捆的 单调栈 刷题记录

原文：https://www.cnblogs.com/jiecaoer/p/11296347.html