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

· · 题解

P5682题解，不喜勿喷

Pascal&C++都有
作为一个ZJOIer，CSP爆炸。虽然没有参加jx重考，但还是心血来潮写一篇题解。

思路：

这题我们先要引进一个思想，想要使a mod b的值变大，那么a<b，因为这样余数才为a，这样的余数更大。
所以我们先找出最大值，例：
4 5 5 6
最大值为6。
再找出次大值（被选过的数我用删除线标起来）：
4 5 5 6
再找出第三大的值，注意，5不可以再选了。
4 5 5 6
那么余数的次大值就是4 mod 6等于4。
注意，当只有两个数的时候，余数次大应该为次大的数。
当这一个数列都只有一种数的时候，这个数列应该输出-1，注意，这里数据太大了，所以不可以用桶的思想来实现。

C++Code: 
#include<bits/stdc++.h>
 using namespace std;
  int max1=-1,max2=-1,max3=-1,n;
  int a[200005];
  int main()
  {
     cin>>n;
     for(int i=1;i<=n;++i)
     {
        cin>>a[i];
        if(a[i]>max1) max1=a[i];//找最大的
     }
     for(int i=1;i<=n;++i)
      if(a[i]>max2&&a[i]!=max1) max2=a[i];  //找次大的
     for(int i=1;i<=n;++i)
      if(a[i]>max3&&a[i]!=max1&&a[i]!=max2) max3=a[i];//找第三大的
     if(max1!=-1&&max2!=-1&&max3==-1) cout<<max2<<endl;
     else if(max1!=-1&&max2==-1&&max3==-1) cout<<-1<<endl;
     else cout<<max3<<endl;  //思路里已经阐述，这里不再阐述
     return 0;
  }
PascalCode: 
var
 n,i,j,max1,max2,max3:longint;
 a:array[0..200005] of longint;
begin
 readln(n);
 max1:=-maxlongint;max2:=max1;max3:=max1;
 for i:=1 to n do
  begin
   read(a[i]);
   if a[i]>max1 then max1:=a[i]; //找最大
  end;
 for i:=1 to n do
  if (a[i]>max2) and (a[i]<>max1) then  max2:=a[i];  //找次大
 for i:=1 to n do
  if (a[i]>max3) and (a[i]<>max1) and (a[i]<>max2) then max3:=a[i]; //找第三大
 if (max1<>-maxlongint) and (max2<>-maxlongint) and (max3=-maxlongint) then writeln(max2)
 else if (max1<>-maxlongint) and (max2=-maxlongint) and (max3=-maxlongint) then writeln(-1)    
 else writeln(max3);//思路里已经阐述，这里不再阐述
end.

各位小哥哥小姐姐，留个赞再走呗。
祝各位CSP 2020RP++