解题思路

问题简述

有 $n$ 种花，第 $i$ 种花的花瓣数为 $a_i$，数量为 $c_i$。
现有 $m$ 枚硬币，每朵花的价格等于其花瓣数（即买一朵花瓣数为 $x$ 的花需要 $x$ 枚硬币）。
要求选出的花中，任意两朵花的花瓣数之差不超过 $1$，问最多能获得的总花瓣数（即总花费，但受限于 $m$，总花费不能超过 $m$，且要最大化总花瓣数）。

核心思想

由于花瓣数之差不超过 $1$，因此选出的花只能包含至多两种相邻的花瓣数，设为 $x$ 和 $x+1$（也可能只有一种）。
对每个可能的 $x$，计算在不超过 $m$ 的前提下，从花瓣数为 $x$ 和 $x+1$ 的花中选出若干朵所能得到的最大总花瓣数，然后取最大值。

算法步骤

1. 读入并排序
   将 $(a_i, c_i)$ 配对，按 $a_i$ 升序排序。

2. 只选一种花
   对每种花瓣数 $x$，若 $x \le m$，则最多能选 $\min(c_x, \lfloor m/x \rfloor)$ 朵，总花瓣数为 $\min(c_x, \lfloor m/x \rfloor) \cdot x$。更新答案。

3. 同时选两种相邻的花
   遍历排序后的列表，对相邻的两种花 $x$ 和 $x+1$（两者都存在时）进行如下计算：

   • 计算最多能选的 $x$ 花瓣花的数量：$k_1 = \min(c_x, \lfloor m/x \rfloor)$
   • 剩余硬币：$rem = m - k_1 \cdot x$
   • 计算最多能选的 $x+1$ 花瓣花的数量：$k_2 = \min(c_{x+1}, \lfloor rem/(x+1) \rfloor)$
   • 此时剩余硬币：$rem' = m - (k_1 x + k_2 (x+1))$
   • 尝试将部分已选的 $x$ 花瓣花替换为 $x+1$ 花瓣花：
     每替换一朵，总花瓣数增加 $1$，同时多花 $1$ 枚硬币。
     最多可替换的次数为：$$r = \min(k_1,\; c_{x+1} - k_2,\; rem')$$
   • 替换后的总花瓣数为：$$total = k_1 x + k_2 (x+1) + r$$ 用 $total$ 更新答案。

4. 输出答案。

正确性证明

• 只选一种花 的情况显然正确。
• 同时选两种花：
  首先，在不超过 $m$ 的前提下，先尽可能多地选便宜的 $x$ 花（得到 $k_1$），然后在剩余硬币中尽可能多地选 $x+1$ 花（得到 $k_2$），这是一个可行解。
  在此基础上，任何将一朵已选的 $x$ 花替换为一朵未选的 $x+1$ 花的操作，都会使总花瓣数增加 $1$，同时总花费增加 $1$。只要还有剩余硬币、还有未选中的 $x+1$ 花、还有已选中的 $x$ 花可供替换，就可以执行替换，并且替换不会破坏可行性。
  因此，通过贪心地执行替换，可以达到最优解。替换次数的上限由三个因素决定：已选 $x$ 花的数量 $k_1$、未选 $x+1$ 花的数量 $c_{x+1} - k_2$、以及剩余硬币数 $rem'$。取最小值 $r$ 即为最多能进行的替换次数，从而得到最优总花瓣数。
  由于我们枚举了所有可能的 $x$，答案一定被包含在内。

复杂度分析

• 排序：$O(n \log n)$
• 遍历并计算：$O(n)$
• 总复杂度：$O(\sum n \log n)$，其中 $\sum n \le 2\times 10^5$，可以轻松通过。
• 空间复杂度：$O(n)$。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

void solve() {
    int n;
    ll m;
    cin >> n >> m;
    vector<pair<ll, ll>> flowers(n);
    for (int i = 0; i < n; ++i) cin >> flowers[i].first;
    for (int i = 0; i < n; ++i) cin >> flowers[i].second;
    sort(flowers.begin(), flowers.end());

    ll ans = 0;

    // 只选一种花
    for (int i = 0; i < n; ++i) {
        ll x = flowers[i].first;
        ll cnt = flowers[i].second;
        if (x > m) continue;
        ll buy = min(cnt, m / x);
        ans = max(ans, buy * x);
    }

    // 同时选两种相邻的花
    for (int i = 0; i < n - 1; ++i) {
        ll x = flowers[i].first;
        ll cx = flowers[i].second;
        ll y = flowers[i + 1].first;
        ll cy = flowers[i + 1].second;

        if (y != x + 1) continue;  // 只处理相邻对
        if (x > m) continue;

        // 计算 k1, k2, remain'
        ll k1 = min(cx, m / x);
        ll remain = m - k1 * x;
        ll k2 = min(cy, remain / y);
        ll used = k1 * x + k2 * y;
        ll remain2 = m - used;

        // 替换次数 r
        ll r = min({k1, cy - k2, remain2});
        ll total = used + r;  // 每替换一次总花瓣数增加 1
        ans = max(ans, total);
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}