# HDU - 2018杭电ACM集训队单人排位赛 - 3 - Problem E. Sequence

xiaoxiao2021-03-01  9

# Problem E.Sequence

Time Limit: 10000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 220    Accepted Submission(s): 53

Problem Description

We define an element ai in a sequence "good", if and only if there exists a j(1≤j<i) such that aj<ai. Given a permutation p of integers from 1 to n. Remove an element from the permutation such that the number of "good" elements is maximized.

Input

The input consists of several test cases. The first line of the input gives the number of test cases, T(1≤T≤103). For each test case, the first line contains an integer n(1≤n≤106), representing the length of the given permutation. The second line contains n integers p1,p2,⋯,pn(1≤pi≤n), representing the given permutation p. It’s guaranteed that ∑n≤2×107.

Output

For each test case, output one integer in a single line, representing the element that should be deleted. If there are several answers, output the minimal one.

Sample Input 2 1 1 5 5 1 2 3 4

Sample Output 1 5

AC 代码

#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=1e6+10; int a[maxn], cnt[maxn]; int main() { int T; scanf("%d",&T); int n; while(T-- && ~scanf("%d",&n)) { mem(cnt,0); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int l,r,pre; l=r=INT_MAX; for(int i=1;i<=n;i++) { if(r<a[i]) cnt[i]++; else if(l<a[i]) r=a[i], cnt[i]++, cnt[pre]++; else r=l, l=a[i], pre=i; } pre=1; for(int i=2;i<=n;i++) if(cnt[i]==cnt[pre]&&a[pre]>a[i] || cnt[pre]>cnt[i]) pre=i; printf("%d\n",a[pre]); } return 0; }