模板题：2500 后面第一个大于
一般要正着看不出来，反着想，有的人也叫做正难则反。
有思维的一道题：1279 扔盘子
暴力会TLE
数据有点水，反着写的可以拿95%
1 //垃圾数据从井底倒着网上数盘子居然能过19个测试点 2 //但是提供给我们一种思路就是，明知道正着肯定会错时逆向解题也许能拿更多的分 3 #include<bits/stdc++.h> 4 using namespace std; 5 const int maxN=50005; 6 int n, m; 7 int w[maxN], d[maxN]; 8 int main() { 9 cin>>n>>m; 10 for(int i=0; i<n; i++)cin>>w[i]; 11 for(int i=1; i<=m; i++)cin>>d[i]; 12 if(w[0]<d[1])cout<<0; //下载测试点数据：4 4 3 6 8 9 4 6 2 2 13 else { 14 int j=1; 15 for(int i=n-1; i>=0; i--) { 16 if(d[j]<=w[i]) { 17 j++; 18 } 19 } 20 cout<<j-1; 21 } 22 return 0; 23 }
正着写用到所谓单调栈，比较有意思
1 //很好的一道关于单调栈的题 2 #include <bits/stdc++.h> 3 using namespace std; 4 const int N=50005; 5 int w[N],d[N]; 6 stack<int>s; 7 int main() { 8 int n,m,ans=0,tmp=0x3f3f3f3f; 9 scanf("%d%d",&n,&m); 10 for(int i=0; i<n; i++)scanf("%d",&w[i]); 11 for(int i=0; i<m; i++)scanf("%d",&d[i]); 12 for(int i=0; i<n; i++) { 13 if(w[i]<=tmp)tmp=w[i];//注意此处怎样将栈变成单调栈 14 s.push(tmp); 15 } 16 int cur=0; 17 while(!s.empty()&&cur<m) { 18 if(s.top()<d[cur]) { 19 s.pop(); 20 continue; 21 } 22 ans++; 23 s.pop(); 24 cur++; 25 } 26 printf("%d ",ans); 27 return 0; 28 }