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

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

解题思路：首先要明白，一个好数 a 即在它自己前面（不包括它自己）中若存在一个比它小的数 b 即该数 a 为好数；一个不好数，它总是它之前(包括它自己)出现的所有数中最小的。

考虑删除一个好数还是不好数：

删除一个好数：则总的好数数量将减少一个(因为删除它后能影响到的好数仅有它自己)。

删除一个不好数：考虑删除这个不好数后能影响到的好数有几个，那么总的好数数量就减少几个。

维护：通过 一个最小数 和 一个次小数 的维护即可得到每个数据元素的贡献量，最后找到那个贡献最小的数据元素即可。

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;
}