Codeforces 484B Maximum Value(高效+二分)

题目链接:Codeforces 484B Maximum Value

题目大意:给定一个序列,找到连个数ai和aj,ai%aj尽量大,而且ai≥aj

解题思路:类似于素数筛选法的方式,每次枚举aj,然后枚举k,每次用二分找到小于k∗aj而且最大的ai,维护答案,过程中加了一些剪枝。

#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
const int maxn = 1e6+5; int N, a[maxn]; int solve (int x) {
int ret = 0, p = x;
while (p < maxn) {
p += x;
int k = lower_bound(a, a + N, p) - a; if (k == 0) continue;
else k--; if (a[k] <= x) continue; ret = max(ret, a[k] % x);
}
return ret;
} int main () {
scanf("%d", &N);
for (int i = 0; i < N; i++)
scanf("%d", &a[i]);
sort(a, a + N); int ans = 0;
for (int i = N-1; i >= 0; i--) {
if (ans >= a[i] - 1)
break;
if (i < N - 1 && a[i] == a[i+1])
continue;
ans = max(ans, solve(a[i]));
}
printf("%d\n", ans);
return 0;
}
上一篇:去除web项目中的css、js缓存


下一篇:[CSGO]跑图CFG