解法思路

1. 统计相同花瓣数的花朵数量

首先将数组排序，然后统计每个花瓣数 $x$ 的出现次数，记作 $c_x$。
同时，因为总花费不能超过 $m$，所以对于一种花瓣数 $x$，最多只能选取 $\left\lfloor \frac{m}{x} \right\rfloor$ 朵（否则总花瓣数会超过 $m$），但实际数量受 $c_x$ 限制，因此实际可选数量为 $\min(c_x, \lfloor m/x \rfloor)$。

2. 枚举相邻花瓣数的组合

由于任意两朵花的花瓣数之差不超过 $1$，所以选出的花束只可能包含两种相邻的花瓣数 $x$ 和 $x+1$（也可能只包含一种）。

我们可以遍历所有可能的花瓣数 $x$，并枚举选取 $x$ 的数量 $k_1$（$0 \le k_1 \le \min(c_x, \lfloor m/x \rfloor)$）。
此时已花费 $k_1 \cdot x$ 硬币，剩余硬币数为 $m - k_1 \cdot x$。

对于花瓣数 $x+1$，最多可以选取

$$k_2 = \min\left(c_{x+1},\ \left\lfloor \frac{m - k_1 \cdot x}{x+1} \right\rfloor\right) $$

朵。

则该组合的总花瓣数为 $k_1 \cdot x + k_2 \cdot (x+1)$。
对所有 $x$ 和所有可能的 $k_1$ 取最大值即可。

3. 为什么枚举 $k_1$ 的复杂度是 $O(n)$？

对于每个 $x$，$k_1$ 从 $0$ 枚举到 $\min(c_x, \lfloor m/x \rfloor)$。

• 如果 $\lfloor m/x \rfloor \ge c_x$，则枚举次数为 $c_x+1$。
• 如果 $\lfloor m/x \rfloor < c_x$，则枚举次数为 $\lfloor m/x \rfloor+1$，此时因为 $x$ 很大，$\lfloor m/x \rfloor$ 很小，总和仍然受限于 $n$ 和不同 $x$ 的个数。

事实上，所有 $x$ 的 $\min(c_x, \lfloor m/x \rfloor)$ 之和不超过 $n + \text{不同}x\text{的个数}$，而不同 $x$ 的个数也 $\le n$，因此总枚举次数为 $O(n)$。

排序的复杂度为 $O(n \log n)$，因此总复杂度为 $O(n \log n)$，满足题目要求（所有测试用例的 $n$ 之和不超过 $2 \times 10^5$）。

4. 边界处理

• 当没有 $x+1$ 的花朵时，$c_{x+1}=0$，此时 $k_2=0$，相当于只选花瓣数为 $x$ 的花。
• 当 $k_1=0$ 时，相当于只选花瓣数为 $x+1$ 的花。
• 注意 $m$ 可能非常大（$10^{18}$），但 $x$ 最小为 $1$，故 $\lfloor m/x \rfloor$ 在计算时需要用 64 位整数。

算法步骤

1. 读入 $t$ 组测试用例。
2. 对每个测试用例：
   • 读入 $n, m$ 和数组 $a$。
   • 对 $a$ 排序。
   • 统计每个不同花瓣数 $x$ 及其出现次数 $c_x$，存储到列表 pairs 中（例如 $(x, c_x)$）。
   • 初始化答案 $ans = 0$。
   • 遍历每个 $x$（注意同时要能访问 $c_{x+1}$，可以再存储一个映射或直接按顺序处理）：
     • 设当前花瓣数为 $x$，数量为 $c_x$；下一个花瓣数为 $x' = x+1$，数量为 $c_{x'}$（若不存在则 $c_{x'}=0$）。
     • 计算 $limit = \min(c_x, \lfloor m/x \rfloor)$。
     • 对于 $k_1 = 0$ 到 $limit$：
       • 剩余硬币 $rem = m - k_1 \cdot x$。
       • 若 $rem < 0$ 则跳出。
       • $k_2 = \min(c_{x'},\ \lfloor rem / (x+1) \rfloor)$。
       • 更新 $ans = \max(ans,\ k_1 \cdot x + k_2 \cdot (x+1))$。
   • 输出 $ans$。

示例验证

以第一个测试用例为例：
$n=5,m=10$，花朵花瓣：$[1,1,2,2,3]$
排序后得到：$1$ 出现 $2$ 次，$2$ 出现 $2$ 次，$3$ 出现 $1$ 次。

• 枚举 $x=1$：$c_1=2$，$\lfloor 10/1 \rfloor=10$，$limit=2$

  • $k_1=0$：$rem=10$，$k_2=\min(2,\lfloor10/2\rfloor=5)=2$，总花瓣 $0+2\times2=4$
  • $k_1=1$：$rem=9$，$k_2=\min(2,\lfloor9/2\rfloor=4)=2$，总花瓣 $1+4=5$
  • $k_1=2$：$rem=8$，$k_2=\min(2,\lfloor8/2\rfloor=4)=2$，总花瓣 $2+4=6$

• 枚举 $x=2$：$c_2=2$，$\lfloor10/2\rfloor=5$，$limit=2$

  • $k_1=0$：$rem=10$，$k_2=\min(1,\lfloor10/3\rfloor=3)=1$，总花瓣 $0+3=3$
  • $k_1=1$：$rem=8$，$k_2=\min(1,\lfloor8/3\rfloor=2)=1$，总花瓣 $2+3=5$
  • $k_1=2$：$rem=6$，$k_2=\min(1,\lfloor6/3\rfloor=2)=1$，总花瓣 $4+3=7$

• 枚举 $x=3$：$c_3=1$，$\lfloor10/3\rfloor=3$，$limit=1$

  • $k_1=0$：$rem=10$，$k_2=0$（无 $x+1=4$），总花瓣 $0$
  • $k_1=1$：$rem=7$，$k_2=0$，总花瓣 $3$

最大值为 $7$，与样例输出一致。

完整题解代码框架（C++ 风格）

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        bool hasZero = false;
        int negCount = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (a[i] == 0) hasZero = true;
            else if (a[i] < 0) negCount++;
        }
        // 乘积为负：奇数个负数且无0
        if (!hasZero && negCount % 2 == 1) {
            cout << "0\n";
        } 
        // 乘积为0
        else if (hasZero) {
            cout << "0\n";
        } 
        // 乘积为正
        else {
            cout << "1\n";
            // 输出任意一个元素改成0
            cout << "1 0\n";
        }
    }
    return 0;
}

复杂度分析

• 排序：$O(n \log n)$
• 统计和枚举：$O(n)$（因为每个花朵最多被作为 $k_1$ 枚举一次）
• 总复杂度：$O(n \log n)$，满足题目限制。