TRZ_2007 的博客

TRZ_2007 的博客

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

posted on 2019-11-24 14:58:54 | under 题解 |

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:用法
    $unique$ 的用法如下:

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