我们先理解题意,大致意思是:
给你一个序列让你组成一个中间有一个数,左侧递增右侧递减的数列。
从这道题的题意来看,大概思路是:
1. 我们要将最大值设为中间的数,然后左右两端尽可能的小。
2. 跑两遍循环,分别为左边的递增边的递减。
3. 还有,因为一个数可以出现很多次,我们需要一个 vis 数组来存储此位置是否被使用过。
4. 最后,我采用的是开两个 vector 来存储左边的上升,和右边的下降。
AC 代码
#include<bits/stdc++.h>
using namespace std;
int a[100010];
bool vis[100010];
vector<int> up;//上升部分
vector<int> down;//下降部分
int main(){
int m;
cin>>m;
for(int i=1;i<=m;i++){
cin>>a[i];
}
sort(a+1,a+m+1);
down.push_back(a[m]);
vis[m]=true;
for(int i=m-1;i>=1;i--){
if(a[i]<a[i+1]){
down.push_back(a[i]);
vis[i]=true;
}
}
int top=0;
for(int i=1;i<=m;i++){
if(vis[i]!=true&&a[i]>top&&a[i]<a[m]){
vis[i]=true;
top=a[i];
up.push_back(a[i]);
}
}
cout<<up.size()+down.size()<<endl;
for(int i=0;i<up.size();i++){
cout<<up[i]<<" ";
}
for(int i=0;i<down.size();i++){
cout<<down[i]<<" ";
}
return 0;
}
代码较为丑陋,仅供参考。
完结撒花。