F. Bomb - Codeforces Round 962 (Div. 3)

Lastmod: 2024-07-30 周二 23:44:10

https://codeforces.com/contest/1996/problem/F

题目大意

给定 $n \le 2 \cdot 10^5$ 的两个数组 $a$ 和 $b$。可以执行 $k \le 10^9$ 次操作，每次操作选择某个 $i$ 然后 $ans += a[i]$，之后 $a[i] = max(0, a[i] - b[i])$。问最大的 $ans$ 是多少。

简要题解

题目贪心的策略是显然的，只需要选当前最大的数即可。易证，如果某个 $x$ 被选的最优解中有比它大的 $y$ 没有被选，则选 $y$ 而不选 $x$ 的结果会更好。也不存在更多的选某个数把其选的更小而留着更大的数不选的情况，同样可以发现，选大的数更好。

但是这题 $k$ 很大，直接模拟是不行的。

于是我们可以通过二分确定最后剩下的最大的 $val$ 是多少，这样比它大的所有值都应该是被选的。而等于 $val$ 的数如果没有选够 $k$ 个则需要尽量的选。

复杂度

$T$：$O(n \log max(a))$

$S$：$O(n)$

代码实现

二分不超过 $k$ 个选取的最小 $v$

#include <bits/stdc++.h>
using namespace std;

int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();

using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;

template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) { 
    return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) { 
    return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z 
    if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
    if(x<z) { y=x; x=z; } else if(y<z) y=z; }

// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());

/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/

LL sum_seq(int l, int r, int d) {
  return 1LL * (l + r) * ((r - l) / d + 1) / 2;
}

void solve() {
  int n, k; cin >> n >> k;
  vector<int> a(n), b(n);
  for (int& i : a) cin >> i;
  for (int& i : b) cin >> i;

  LL tot = 0;
  for (int i = 0; i < n; i++) {
    tot += (a[i] + b[i] - 1) / b[i];
  }

  if (tot <= k) {
    LL sum = 0;
    for (int i = 0; i < n; i++) {
      int cnt = a[i] / b[i];
      sum += sum_seq(a[i] - b[i] * cnt, a[i], b[i]);
    }
    cout << sum << '\n';
    return;
  }
  
  int mx = *max_element(a.begin(), a.end());
  int l = 1, r = mx + 1;
  int ans = r, mid;

  auto check = [&](int mid) {
    LL cnt = 0;
    for (int i = 0; i < n; i++) {
      if (a[i] <= mid) continue;
      cnt += (a[i] - mid + b[i] - 1) / b[i];
    }
    return cnt;
  };

  while (l <= r) {
    mid = (l + r) >> 1;
    if (check(mid) <= k) {
      ans = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }

  // cerr << ans << '\n';

  LL sum = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] <= ans) continue;
    int cnt = (a[i] - ans + b[i] - 1) / b[i];
    k -= cnt;
    sum += sum_seq(a[i] - b[i] * (cnt - 1), a[i], b[i]);
  }

  sum += 1LL * k * ans;
  cout << sum << '\n';
}

int main() {
  int t = 1; 
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

二分多于 $k$ 个选取的最大 $v$，本质上是一样的。

#include <bits/stdc++.h>
using namespace std;

int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();

using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;

template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) { 
    return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) { 
    return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z 
    if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
    if(x<z) { y=x; x=z; } else if(y<z) y=z; }

// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());

/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/

LL sum_seq(int l, int r, int d) {
  return 1LL * (l + r) * ((r - l) / d + 1) / 2;
}

void solve() {
  int n, k; cin >> n >> k;
  vector<int> a(n), b(n);
  for (int& i : a) cin >> i;
  for (int& i : b) cin >> i;

  LL tot = 0;
  for (int i = 0; i < n; i++) {
    tot += (a[i] + b[i] - 1) / b[i];
  }

  if (tot <= k) {
    LL sum = 0;
    for (int i = 0; i < n; i++) {
      int cnt = a[i] / b[i];
      sum += sum_seq(a[i] - b[i] * cnt, a[i], b[i]);
    }
    cout << sum << '\n';
    return;
  }
  
  int mx = *max_element(a.begin(), a.end());
  int l = 1, r = mx;
  int ans = 0, mid;

  auto check = [&](int mid) {
    LL cnt = 0;
    for (int i = 0; i < n; i++) {
      if (a[i] < mid) continue;
      cnt += (a[i] - mid) / b[i] + 1;
    }
    return cnt >= k;
  };

  while (l <= r) {
    mid = (l + r) >> 1;
    if (check(mid)) {
      ans = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }

  LL sum = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] < ans) continue;

    int cnt = (a[i] - ans) / b[i] + 1;

    sum += sum_seq(a[i] - b[i] * (cnt - 1), a[i], b[i]);
    k -= cnt;
  }

  // cerr << ans << ' ' << sum << ' ' << k << endl;

  sum += 1LL * k * ans;

  cout << sum << '\n';
}

int main() {
  int t = 1; 
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

对拍数据生成

#include <bits/stdc++.h>
using namespace std;

int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();

using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;

template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
    if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
    if(x<z) { y=x; x=z; } else if(y<z) y=z; }

mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());

/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/

inline int rndi() { return rnd(); }
inline int rndi(int n) { return rnd()%n; }
inline int rndi(int l, int r) { return rnd() % (r - l + 1) + l; }
inline LL rndll() { return rnd_64(); }
inline LL rndll(LL n) { return rnd_64() % n; }
inline LL rndll(LL l, LL r) { return rnd_64() % (r - l + 1) + l; }
inline char rndc() { return rnd() % 26 + 'a'; }
inline char rndC() { return rnd() % 26 + 'A'; }
inline char rnddig() { return rnd() % 10 + '0'; }
inline char rndcha() {
  int v = rnd() % 52;
  return v < 26 ? v + 'a' : (v - 26 + 'A');
}

template<typename T>
void shuffle(vector<T>& vec) { shuffle(vec.begin(), vec.end(), rnd); }

vector<int> rnd_permu(int n, int from = 0) {
  vector<int> vec(n);
  iota(vec.begin(), vec.end(), from);
  shuffle(vec);
  return vec;
}

void solve() {
  int n = 5;
  int k = rndi(5, 10);
  cout << n << ' ' << k << '\n';

  for (int i = 0; i < n; i++) {
    cout << rndi(1, 10) << ' ';
  }
  cout << '\n';

  for (int i = 0; i < n; i++) {
    cout << rndi(1, 10) << ' ';
  }
  cout << '\n';
}

int main() {
  int t = 1; cout << t << '\n';
  while (t--) {
    solve();
  }
  return 0;
}

Prev: E. Decode - Codeforces Round 962 (Div. 3)
Next: G. Penacony - Codeforces Round 962 (Div. 3)