Codeforces 731F Video Cards

链接

传送门

题意

给出\(n(1 \leq n \leq 200000)\)个数，选择其中一个\(a_i(1 \leq a_i \leq 200000)\)，将其他的数字都减少到ai的非负整数倍，输出所有数字和的最大值。

思路

对于枚举每个数字，然后二分它所有倍数的个数。 因为相同的数字可以忽略，二分的次数为\(O (n\log n)\)，总的复杂度为\(O(n\log^2n)\)

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int maxn = 200010;

int a[maxn];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  sort(a, a + n);
  LL ans = 0;
  for (int i = 0; i < n; ++i) {
    if (i == 0 || a[i] != a[i - 1]) {
      LL sum = 0;
      int *cur, *pre = a;
      for (int j = 0; j <= a[n - 1]; j += a[i]) {
        cur = lower_bound(a, a + n, j + a[i]);
        sum += j * LL(cur - pre);
        pre = cur;
      }
      ans = max(ans, sum);
    }
  }
  printf("%lld\n", ans);
  return 0;
}