题解 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:
```cpp
#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$的用法如下：
```cpp
int k = unique(a+1,a+n+1) - a;
```
解释：$k$表示数组$a$去重后还剩几个值，后面那一坨东西就把他当做$sort$的用法，最后加一个$ - a$ .
- 2：复杂度
目测$\Theta(n\log n)$
100pts代码：
```cpp
#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);
}
}
```