PAT A1101

45次阅读

共计 770 个字符,预计需要花费 2 分钟才能阅读完成。

这道题的题目和之前的 PAT 题目相同,也是采用打表的方法;先预先算好所有的元素;建立两个数组,left,right;left 从左到右遍历,索引 index 装从左到 index 中最大的元素;right 从右到左遍历,索引 index 装从右到 index 中最小元素;之后从 0~n 比较 left,right 相应的成员,也就是看左边最大和右边最小是否符合题目规范
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
const int maxn=100010;
const int INF=0x3fffffff;
int data[maxn];
int left1[maxn];
int right1[maxn];
int ans[maxn];
int num=0;
int n;
int main(){
scanf(“%d”,&n);
for(int i=0;i<n;i++){
scanf(“%d”,&data[i]);
}
left1[0]=0;
for(int i=1;i<n;i++){
left1[i]=max(left1[i-1],data[i-1]);
}
right1[n-1]=INF;
for(int i=n-2;i>=0;i–){
right1[i]=min(right1[i+1],data[i+1]);
}
for(int i=0;i<n;i++){
if(left1[i]<data[i]&&right1[i]>data[i]){
ans[num++]=data[i];
}
}
printf(“%d\n”,num);
for(int i=0;i<num;i++){
printf(“%d”,ans[i]);
if(i<num-1)
printf(” “);
}
printf(“\n”);
system(“pause”);
return 0;
}

正文完
 0