Time Limit: 5000 ms Memory Limit: 65536 KiB
Submit Statistic Discuss
Problem Description
We define an element aia_ia i in a sequence “good”, if and only if there exists a j(1≤j<i)j(1\le j < i)j(1≤j<i) such that aj<aia_j < a_ia j <a i . Given a permutation ppp of integers from 111 to nnn. 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)T(1\le T\le 10^3)T(1≤T≤10 3 ). For each test case, the first line contains an integer n(1≤n≤106)n(1\le n\le 10^6)n(1≤n≤10 6 ), representing the length of the given permutation. The second line contains nnn integers p1,p2,⋯,pn(1≤pi≤n)p_1,p_2,\cdots,p_n(1\le p_i\le n)p 1 ,p 2 ,⋯,p n (1≤p i ≤n), representing the given permutation ppp. It’s guaranteed that ∑n≤2×107\sum n\le 2\times 10^7∑n≤2×10 7 .
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 emm 我觉得想出来这种解法的人是神仙，希望我以后也能成为神仙。 题意； 有N个数，输入N个数，组成一个排列，我们定义如果一个数，它大于它前面的任意一个数，那么我们称这个数为好数，现在让你从n个数中去掉一个数，使好数增加。 看完题解，得知可以维护一个最小值和一个次小值（如果一个数小于最小值，那么此时这个数成为了最小值，原来的最小值变成了次小值；如果一个数大于最小值小于次小值，那么这个数本身就是好数，同时最小数维护了一个好数；如果一个数大于次小值，那么这个数本身就是一个好数），然后用输入的数进行比较，维护一个从c[i]用于记录一个数可以维护几个好数，最后找出维护好数个数最小的数，然后输出即可。 分类讨论是难点；
#include<stdio.h> #include<string.h> long long ans=99999999,minf=99999999,minn=99999999; long long a; long long c[1000100]; int main() { int t; scanf("%d",&t); while(t--) { ans=99999999,minf=99999999,minn=99999999; long long i; int flag; memset(c,0,sizeof(c)); long long n; scanf("%lld",&n); for(i=1;i<=n;i++) {scanf("%lld",&a); if(a<=minn) { minf=minn; minn=a; } else if(a>=minn&&a<minf) { c[a]++; c[minn]++;//维护好数的个数加1 minf=a; } else if(a>=minf) { c[a]++;//本身就是好数 } } flag=minf; for(i=1;i<=n;i++) { if(c[i]<ans) ans=c[i],flag=i; } printf("%d\n",flag); } return 0; }