题解 P5682 【次大值【民间数据】】

TRZ_2007 · 2019-11-24 14:58:54 · 题解

Solution

给你一个长度为n的数组，求将所有的a_i \text{ mod } a_j (i,j\le n)去重后的第二大值。

这题可以分点拿份，先看70tps的解法：
开下一个数组book，存下每一个a_i \text{ mod } a_j，然后暴力求解。

70pts:

#include <bits/stdc++.h>
#pragma GCC optimize(3)

using namespace std;

const int N = 2e5+9;
const int Inf = 1e5+9;

int a[N],n,Max,sum;
bool book[Inf];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            book[a[i] % a[j]] = true;
            Max = max(Max,a[i] % a[j]);
        }
    }
    for(int i=Max;i>=1;i--) {
        if(book[i] == true) sum++;
        if(sum == 2) {
            printf("%d\n",i);
            exit(0);
        }
    }
    if(sum < 2) {
        puts("-1");
        exit(0);
    }
}

因为数组开不下10^9的内存，且n \le 2 \times 10^5的数据\Theta(n^2)的算法也会爆炸。

100pts解法：

其实较大的a_i \text{ mod } a_j必定是a_i，因为a_i \text{ mod } a_j必定小于a_i。所以这题就转换成了要你求a排序去重后的第二大值。

剩下来的就认识函数unique（去重函数）即可。

• 1：用法

  ```cpp int k = unique(a+1,a+n+1) - a; ``` 解释：$k$表示数组$a$去重后还剩几个值，后面那一坨东西就把他当做$sort$的用法，最后加一个$ - a$ .

• 2：复杂度 目测\Theta(n\log n)

100pts代码：

#include <bits/stdc++.h>
#pragma GCC optimize(3)

using namespace std;

const int N = 2e5+9;

int a[N],n;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    int k = unique(a+1,a+n+1) - a;//这行语句过后a早已被自动去重。
    if(k <= 2) {
        puts("-1");
        exit(0);
    }
    else {
        printf("%d\n",a[k - 3]);
        exit(0);
    }
}