|
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("%dn",res); return 0; } |
在lower_bound之后如果加入了多余的判断（判断pos的位置等等），就会T，如果没有用unique来压缩输入，就会T。
总觉得很寸，应该是数据做的有漏洞。
解法的思路就是先从小到大排序，然后从第一项开始，借用素数筛法的思路，对于每个数检查以这个数的倍数为终点的各个区间，然后找出每个区间之内离终点最近的数，更新答案。找终点的过程使用了二分搜索，STL自带的lower_bound和upper_bound就能很好地工作，使用upper_bound的话还有一个小窍门就是把搜索目标设成目标－1，这样的话搜索完落在的点就和lower_bound是一样的了。
