自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:52:45，当前版本为作者最后更新于2024-02-09 12:52:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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
*/