题意
给你一串数，让你找出一组(i,j)，使得在保证第i项大于等于第j项的同时，第i项mod第j项最大，求这个最大值。
思路
要有一种转换的思维，余数最大的话，可以另一个方向进行考虑，a%b=c的话，a可以看成是kb+c,这个里面b,c是已知的，这个k可以枚举，这样就把求余数这个事情转换成了枚举／搜索，换一个思路问题可能就突破了。
对给出的数列sort一下，unique一下，erase一下，这样就有效的避免了重复数据的干扰（如果你不unique可能会被这个题的某组坑数据给弄T），而且sort完才能做。sort好之后，我们挨个数枚举，对于每个数k，我们考虑这个数列上0~k,k~2k,2k~3k,…这些个小区段，每个小区段中最大的那个数 mod k可能是最大的，我们挨个数挨个区段去枚举就可以了。
但是暴力枚举是过不了的，我们就把在数列中找k,2k,…这个过程改成二分搜索，这样复杂度降为nlogn就行了。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; int seq[200005]; int main(){ int n = 0; scanf(" %d",&n); memset(seq, 0, sizeof(seq)); for (int i = 1; i <= n; i++) { scanf(" %d",&seq[i]); } n = unique(seq+1,seq+1+n) - seq - 1; sort(seq+1, seq+1+n); int res = 0; for (int i = 1; i <= n; i++) { //opt if (seq[i] == 1) { continue; } if (res >= seq[i]-1) { continue; } int k = 0; while (k * seq[i] <= seq[n]) { k++; int pos = lower_bound(seq+1,seq+1+n, k*seq[i]) - seq; pos--; if(pos >= i) res = max(res,seq[pos]%seq[i]); //quit if (res >= seq[i]-1) { break; } } } printf("%d\n",res); return 0; } |
