P10098 [ROIR 2023] 地铁建设 (Day 2)

记录147

#include<bits/stdc++.h> using namespace std; #define ll long long // 使用long long处理大数 const int MAXN=105; int n; ll p; ll z[MAXN],a[MAXN],b[MAXN]; // 存储每个发动机的参数 // 验证函数：判断电压为x时，总功率是否>=p bool check(ll x) { ll total_power=0; for(int i=1;i<=n;i++) { if(x<=z[i]) { // 第一模式：功率 = a_i * x total_power+=a[i]*x; } else { // 第二模式：功率 = a_i * z_i + b_i * (x - z_i) total_power+=a[i]*z[i]+b[i]*(x-z[i]); } // 剪枝：如果当前总功率已经达到p，直接返回true，防止溢出 if(total_power>=p) return true; } return total_power>=p; } int main() { ios::sync_with_stdio(false); // 关闭同步，加速IO cin.tie(0); cin>>n>>p; for(int i=1;i<=n;i++) { cin>>z[i]>>a[i]>>b[i]; } // 二分答案：寻找满足条件的最小电压 ll left=1,right=(ll)2e12,ans=right; // 上界设为2*10^12 while(left<=right) { ll mid=(left+right)/2; if(check(mid)) { // 如果mid可行，尝试更小的电压 ans=mid; right=mid-1; } else { // 如果mid不可行，需要更大的电压 left=mid+1; } } cout<<ans<<"\n"; return 0; } //2e12 在 C++ 中默认是一个 double（浮点数）类型。当你把它赋值给 long long 类型的变量（比如 right）时，编译器会自动把它转换为整数。 //它也是用 64 个二进制位来存一个小数。但它采用了“科学计数法”的存储方式（1位符号位 + 11位指数位 + 52位尾数位）。因为指数位能表示极大的范围，大概1e15

题目传送门https://www.luogu.com.cn/problem/P10098

前言

我是一名专注信奥赛（CSP-J/S、NOIP）的教练。

• 如果你觉得这篇题解对你有帮助，欢迎点击关注我的CSDN账号，我会持续更新高质量算法解析。
• 我深知算法思维的构建远比单纯通过题目更重要，本系列题解不局限于AC代码的堆砌，而是致力于拆解题目背后的逻辑链条与核心知识点
• 备赛路上若遇瓶颈，欢迎随时评论或私信，我将甄选典型疑难问题，通过视频讲解或撰写专项文章的形式，为你提供深度答疑。

核心解题思路

这道题是一道非常经典的二分答案 + 贪心验证问题。

1. 问题转化与单调性分析：
   题目要求找到“最小的 L”，使得能在 k 次操作内关掉所有的灯。直接去求这个最小 L 比较困难，但如果我们反过来思考：假设 L 已经确定，我们能不能判断 k 次操作够不够？
   这里存在一个关键的单调性：如果长度为 L 的操作能够完成任务，那么长度为 L+1 的操作一定也能完成任务（因为覆盖范围更大了，只会让关灯更容易）。这种单调性为使用“二分答案”提供了完美的理论基础。

2. 算法设计（二分 + 贪心）：

   • 二分答案：L 的取值范围在 [1, n] 之间。我们在该区间内进行二分查找。
   • 贪心验证（check函数）：对于当前假设的 L，我们需要判断 k 次操作是否足够。这里采用最直观的贪心策略：从左到右扫描灯的状态，一旦遇到一盏亮着的灯（'1'），就必须以这盏灯为起点，执行一次关灯操作。因为如果不关掉这盏灯，后续的操作（起点在更右边）永远无法覆盖到它。这种“见亮必关，且尽量靠左关”的策略，是保证操作次数最少的最优解。

代码分块详细解释

1. 头文件、全局变量与贪心验证函数

#include<bits/stdc++.h> using namespace std; #define ll long long // 使用 long long 防止溢出 int n, k; string s; // 存储灯的初始状态 // 验证函数：判断长度为 L 的操作是否能在 k 步内关灯 bool check(int L) { // 复制一份原始灯的状态，因为验证过程会修改灯的状态 string temp = s; int ops = 0; // 记录操作次数 for(int i = 0; i < n; i++) { // 如果当前灯是亮的，必须进行一次操作 if(temp[i] == '1') { ops++; if(ops > k) return false; // 操作次数超限，直接返回 false // 贪心：从当前位置 i 开始，往后关掉 L 盏灯 for(int j = i; j < i + L && j < n; j++) { temp[j] = '0'; } } } return true; // 操作次数在 k 以内，返回 true }

• 详细分析：check函数是本题的核心。
  • 状态备份：因为验证过程会实际模拟关灯（将 '1' 变为 '0'），为了不破坏原始数据s，必须使用temp进行备份。
  • 贪心模拟：从左往右遍历temp。当遇到temp[i] == '1'时，说明这盏灯还没被关掉。根据贪心原则，我们必须在位置i执行一次操作。操作次数ops加 1，如果超过 k 直接返回失败。
  • 关灯操作：从位置i开始，将接下来连续的 L 盏灯全部置为 '0'。注意边界条件j < n，防止数组越界。

2. 主函数：多组测试与二分框架

int main() { ios::sync_with_stdio(false); // 关闭同步，加速 IO cin.tie(0); int T; cin >> T; while(T--) { cin >> n >> k; cin >> s; // 二分答案：寻找最小的 L int left = 1, right = n, ans = n; while(left <= right) { int mid = (left + right) / 2; if(check(mid)) { // 如果 mid 可行，尝试更小的 L ans = mid; right = mid - 1; } else { // 如果 mid 不可行，需要更大的 L left = mid + 1; } } cout << ans << "\n"; } return 0; }

• 详细分析：主函数处理了多组测试数据，并搭建了标准的二分答案框架。
  • 二分边界：L 的最小可能值是 1，最大可能值是 n（一次操作关所有灯）。
  • 收缩逻辑：如果check(mid)返回 true，说明当前的 L 是可行的，但这不一定是“最小”的，所以我们将ans记录为mid，并尝试在左半区间（更小的 L）继续寻找（right = mid - 1）。如果返回 false，说明 L 太小了，k 次操作根本关不完，必须增大 L（left = mid + 1）。

核心逻辑总结表