P9889 [ICPC2018 Qingdao R] Plants vs. Zombies

· · 题解

P9889 [ICPC2018 Qingdao R] Plants vs. Zombies

*目前为止，本题的所有题解均没有给出贪心的正确性证明。这样不求甚解的态度是需要避免的。

二分高度 h 求出每个位置至少走多少次，记作 c_i = \lceil \frac h {a_i} \rceil ，并计算达到该目标至少走多少次。

因为 c_i > 0，所以一定会走到最右侧。考虑贪心，如果当前位置 p 左侧还需要走，那么往左走，否则往右走。

证明

如果左侧已经不需要走，那么往左走显然是不优的。

如果左侧需要走，那么 p\geq 2。考虑接下来的路径 P，若 P 在当前这一步向右走，则它总会回到 p 并向左走。

  • 如果向左走之后仍回到 p，那么将 P 在 p 及其左边的这一段平移到当前这一步。
  • 如果向左走之后不回到 p，那么：
    • 若 p = 2，则路径最终会停在 1，将 p\to Q\to p\to 1 调整为 p\to 1\to p\to Q ^ R 即可，其中 Q ^ R 是 Q 翻转后的结果。
    • 若 p > 2，根据贪心过程，如果不是位置 p - 2 已经达到目标，路径不会走到 p，于是路径最终会停在 p - 1，类似 p = 2 证明即可。这部分需要归纳以保证正确性：p 正确推出 p + 1 的前提。

于是，对于任意一条最优路径，总可以将其每一步依次调整为上述贪心过程走过的路径，这也就证明了贪心的正确性。\square

贪心过程直接模拟即可，注意路径最终可能停在 n - 1，并注意中途累计的步数可能很大，需要在不合法时立刻停止。

时间复杂度 \mathcal{O}(n\log V)。

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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdi = pair<double, int>;
using pdd = pair<double, double>;
using ull = unsigned long long;
using LL = __int128_t;

#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;

// ---------- templates above ----------

constexpr int N = 1e5 + 5;

ll n, m, a[N], f[N], g[N];
bool check(ll x) {
  ll nxt = 0, res = 0;
  for(int i = 1; i <= n; i++) {
    ll cnt = (x - 1) / a[i] + 1 - nxt;
    if(cnt > 0 || i < n) res++, cnt--;
    cnt = max(cnt, 0ll);
    res += cnt * 2, nxt = cnt;
    if(res > m) return 0;
  }
  return 1;
}
void solve(int T) {
  cin >> n >> m;
  for(int i = 1; i <= n; i++) cin >> a[i];
  if(n > m) {
    cout << "0\n";
    return;
  }
  ll l = 1, r = m * 1e5;
  while(l < r) {
    ll mid = l + r + 2 >> 1;
    if(check(mid)) l = mid;
    else r = mid - 1;
  }
  cout << l << "\n";
}

bool Med;
signed main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  int T = 1;
  cin >> T;
  while(T--) solve(T);
  fprintf(stderr, "%.3lf ms\n", 1e3 * clock() / CLOCKS_PER_SEC);
  return 0;
}

/*
g++ a.cpp -o a -std=c++14 -O2 -DALEX_WEI
*/