题解：学而思编程 清虚幻境大危机！

【题目来源】

学而思编程：清虚幻境大危机！

【题目描述】

幻境遭遇了多次时空风暴！时空风暴每次都会在相同位置产生裂缝，共 \(n\) 条裂缝。为了防止清虚幻境被破坏，为了保护幻境和平，皮皮在每个空间裂缝处布置了 \(m\) 重封锁线，每重封锁线由一支部队进行阻击。
已知每处裂缝处各部队的伤害值。每场时空风暴都会在每个裂缝处出现一个魔君，第 \(i\) 次时空风暴降临的魔君护甲值为 \(power_i\)。只有当该魔君受到伤害大于等于 \(power_i\) 时，才能击杀魔君，防止其突破本层封锁线。若魔君突破了 \(m\) 重封锁线，则视为失败。皮皮希望合理布置每处裂缝的部队，使得魔君尽可能早的被击杀，由于每个裂缝相距较远，布阵只能在同一个裂缝中改变部队顺序。
幻境共遭遇了 \(q\) 次时空风暴，请你计算，在皮皮的最佳布防下，每次时空风暴降临的 \(n\) 个魔君最多突破到第几重封锁线？若有魔君突破了 \(m\) 重封锁线，则输出 \(−1\)。

【输入】

第 \(1\) 行，\(2\) 个正整数空格隔开，\(n\) 表示有 \(n\) 条裂缝，\(m\) 表示每个空间裂缝处布置了 \(m\) 重封锁线；

接下来 \(n\) 行，每行 \(m\) 个空格隔开的正整数，第 \(i+1\) 行的 \(m\) 个数据表示在第 \(i\) 处裂缝的 \(m\) 个部队的伤害值；

接下来 \(1\) 行，一个正整数 \(q\) 表示时空风暴产生的次数；

接下来 \(q\) 行，每行 \(1\) 个正整数 \(power_i\) 表示第 \(i\) 次时空风暴降临时每处魔君的护甲值。

【输出】

每行一个数据，表示在皮皮的最佳布防下，每次时空风暴降临的 \(n\) 个魔君最多突破到第几重封锁线？若有魔君突破了 \(m\) 重封锁线，则该行输出 \(−1\)。

【输入样例】

3 4
1 2 3 4
2 3 4 5
3 4 5 6
3
3
10
15

【输出样例】

1
4
-1

【核心思想】

1. 问题分析：给定 \(n\) 条裂缝，每条裂缝有 \(m\) 个部队的伤害值。每次时空风暴的魔君护甲值为 \(power\)，需要在每条裂缝内部调整部队顺序（即选择排列），使得所有裂缝中魔君被击杀的封锁线层数尽可能早（即最小化最大突破层数）。对于每次查询 \(power\)，求最佳布防下魔君最多突破到第几重封锁线。这是一个整数二分问题，核心在于预处理每条裂缝的最优前缀和，再取全局最小值。

2. 算法选择：

   • 贪心排序 + 前缀和：每条裂缝将部队按伤害降序排列，计算前 \(j\) 个部队的伤害前缀和
   • 全局最小值：\(mn[j]\) 表示所有裂缝中前 \(j\) 个部队前缀和的最小值（即最弱的 \(j\) 层封锁）
   • 二分查找：对每次查询 \(power\)，二分查找最小的 \(j\) 使得 \(mn[j] \geq power\)

3. 关键步骤：

   • 初始化：读取 \(n\)、\(m\)，\(mn[1..m]\) 初始化为 \(\infty\)
   • 处理每条裂缝（\(i\) 从 \(1\) 到 \(n\)）：
     • 读取 \(m\) 个伤害值到 \(a[1..m]\)
     • 降序排序 \(a\)（贪心：伤害高的部队放前面，尽快击杀魔君）
     • 计算前缀和：\(a[j] += a[j-1]\)（前 \(j\) 个部队的总伤害）
     • 更新全局最小值：\(mn[j] = \min(mn[j], a[j])\)（所有裂缝中前 \(j\) 层最弱的总伤害）
   • 处理查询（\(q\) 次）：
     • 读取 \(power\)
     • \(k = lower\_bound(mn+1, mn+m+1, power) - mn\)（第一个满足 \(mn[j] \geq power\) 的 \(j\)）
     • 若 \(k > m\)：输出 \(-1\)（所有 \(m\) 层都无法击杀）
     • 否则：输出 \(k\)（第 \(k\) 层即可击杀）
   • 输出每次查询结果

4. 时间/空间复杂度：

   • 时间复杂度：\(O(n \times m \log m + q \log m)\)，每条裂缝排序 \(O(m \log m)\)，查询二分 \(O(\log m)\)
   • 空间复杂度：\(O(n \times m)\)，存储伤害值和前缀和

5. 整数二分的核心思想：

   • 贪心最优性：每条裂缝内部降序排列，确保前 \(j\) 层总伤害最大，使魔君最早被击杀
   • 全局瓶颈：\(mn[j]\) 取所有裂缝前 \(j\) 层前缀和的最小值，代表最不利情况下第 \(j\) 层的总伤害
   • 单调性利用：\(mn[j]\) 随 \(j\) 增大单调不减（增加部队只会增加总伤害），满足二分条件
   • 边界处理：\(lower\_bound\) 找不到时返回 \(m+1\)，对应输出 \(-1\)
   • 适用于多序列优化、前缀和最小值、二分判定类问题

【算法标签】

整数二分

【代码详解】

#include <bits/stdc++.h>
using namespace std;int a[100005];      // 存储每行的临时数据
int mn[100005];     // 存储前j小的前缀和的最小值
bool cmp(int x, int y)
{return x > y;   // 降序排序比较函数
}int main()
{int n, m;       // n: 行数, m: 列数cin >> n >> m;// 初始化mn数组为极大值memset(mn, 0x3f, sizeof(mn));// 处理每一行数据for (int i = 1; i <= n; i++){// 输入当前行的m个数据for (int j = 1; j <= m; j++)cin >> a[j];// 对当前行降序排序sort(a + 1, a + m + 1, cmp);// 计算前缀和for (int j = 1; j <= m; j++)a[j] += a[j - 1];// 更新全局最小值for (int j = 1; j <= m; j++)mn[j] = min(mn[j], a[j]);}// 处理查询int q;cin >> q;while (q--){int power;cin >> power;  // 输入当前能量值// 使用二分查找找到最小的j使得mn[j] >= powerint k = lower_bound(mn + 1, mn + 1 + m, power) - mn;// 处理找不到的情况if (k > m)k = -1;cout << k << endl;}return 0;
}

【运行结果】

3 4
1 2 3 4
2 3 4 5
3 4 5 6
3
3
1
10
4
15
-1