Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
140323 蒋沛霖 最长不下降子序列 C++ 通过 100 12 MS 644 KB 846 2024-03-30 14:28:06

Tests(10/10):


#include <bits/stdc++.h> using namespace std; int n,x[100001],Lis[100001],longest=0; /* 这道题用最长不下降子序列来做 就是用一个维护序列,始终保持最长不下降,相当于单调队列 */ int main() { cin>>n; for(int i=0; i<n; i++) { scanf("%d",&x[i]); if(!i) Lis[longest++]=x[i]; else { if(x[i]<Lis[longest-1])//如果比之前的最大数小的话,就要搜寻队列,寻找代替 { int j=upper_bound(Lis,Lis+longest,x[i])-Lis;//用STL里的upper_bound代替二分寻找 //维护队列的单调性 Lis[j]=x[i]; } else//其他情况直接添加在单调队列即可 { Lis[longest++]=x[i]; } } } printf("%d",longest);//这里longest不用减一,因为前面初始化为0 return 0; }


测评信息:

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0

输入

                    

输出

                    

答案

                    

系统信息

exit code: 0, checker exit code: 0