题目分析
Input:
第一行:一个正整数N(N<=100000)
第二行:N个互不相同的正整数,用空格分隔
Output:
第一行:符合条件的数的个数
第二行:按照升序输出
求解思路
- int类型的数组arr[N]:存放了原始数据
- maxBefore:当前左侧最大值(初始化为-1)
- minBehind:当前右侧最小值(初始化为1000000005)
- int类型的数组res[N]:存放结果
- bool类型的数组flag[N]:flag[i]指示arr[i]是否为我们要找的元素,若是,flag[i]=true;否则flag[i]=false。
- 在输入的时候,假设当前输入为arr[i],判断arr[i]是否大于maxBefore,同时更新maxBefore和flag[i]的值。
- 逆序遍历数组,判断arr[i]是否小于minBehind,若不是,将flag[i]的值更新为false。若此时flag[i]为true,则arr[i]为我们要找的元素,存入res数组中。
- 输出时,若sum为0,则输出空的一行(必须输出空的一行,否则有的样例不能通过);若sum不为0,调用sort()函数,将res数组升序排列后输出。
C++源码
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int N;
int sum = 0;
cin>>N;
bool *flag = new bool[N];
int *arr = new int[N];
int *res = new int[N];
int maxBefore = -1;
int minBehind = 1000000005;
for(int i = 0; i < N; i++)
{
flag[i] = true;
}
for(int i = 0; i < N; i++)
{
cin>>arr[i];
if(arr[i] > maxBefore)
{
maxBefore = arr[i];
}
else
{
flag[i] = false;
}
}
for(int i = N - 1; i >= 0; i--)
{
if(arr[i] < minBehind)
{
minBehind = arr[i];
}
else
{
flag[i] = false;
}
if(flag[i])
{
sum = sum + 1;
res[sum - 1] = arr[i];
}
}
cout<<sum<<endl;
if(sum == 0)
{
cout<<endl;
}
else
{
//res[0..sum-1]
sort(res, res + sum);
for(int i = 0; i < sum; i++)
{
cout<<res[i];
if(i != sum - 1)
{
cout<<" ";
}
}
}
return 0;
}
网友评论