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

记录147#includebits/stdc.h using namespace std; #define ll long long // 使用long long处理大数 const int MAXN105; int n; ll p; ll z[MAXN],a[MAXN],b[MAXN]; // 存储每个发动机的参数 // 验证函数判断电压为x时总功率是否p bool check(ll x) { ll total_power0; for(int i1;in;i) { if(xz[i]) { // 第一模式功率 a_i * x total_powera[i]*x; } else { // 第二模式功率 a_i * z_i b_i * (x - z_i) total_powera[i]*z[i]b[i]*(x-z[i]); } // 剪枝如果当前总功率已经达到p直接返回true防止溢出 if(total_powerp) return true; } return total_powerp; } int main() { ios::sync_with_stdio(false); // 关闭同步加速IO cin.tie(0); cinnp; for(int i1;in;i) { cinz[i]a[i]b[i]; } // 二分答案寻找满足条件的最小电压 ll left1,right(ll)2e12,ansright; // 上界设为2*10^12 while(leftright) { ll mid(leftright)/2; if(check(mid)) { // 如果mid可行尝试更小的电压 ansmid; rightmid-1; } else { // 如果mid不可行需要更大的电压 leftmid1; } } coutans\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代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的二分答案 贪心验证问题。问题转化与单调性分析题目要求找到“最小的 L”使得能在 k 次操作内关掉所有的灯。直接去求这个最小 L 比较困难但如果我们反过来思考假设 L 已经确定我们能不能判断 k 次操作够不够这里存在一个关键的单调性如果长度为 L 的操作能够完成任务那么长度为 L1 的操作一定也能完成任务因为覆盖范围更大了只会让关灯更容易。这种单调性为使用“二分答案”提供了完美的理论基础。算法设计二分 贪心二分答案L 的取值范围在 [1, n] 之间。我们在该区间内进行二分查找。贪心验证check函数对于当前假设的 L我们需要判断 k 次操作是否足够。这里采用最直观的贪心策略从左到右扫描灯的状态一旦遇到一盏亮着的灯1就必须以这盏灯为起点执行一次关灯操作。因为如果不关掉这盏灯后续的操作起点在更右边永远无法覆盖到它。这种“见亮必关且尽量靠左关”的策略是保证操作次数最少的最优解。代码分块详细解释1. 头文件、全局变量与贪心验证函数#includebits/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 次操作根本关不完必须增大 Lleft mid 1。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点状态备份string temp s复制原始灯的状态保证每次check验证时都是基于原始的亮灯状态进行模拟贪心策略if(temp[i]1)触发操作遇到亮灯就立刻以它为起点关灯确保了在给定 L 的情况下使用的操作次数是最少的边界防护j iL j n限制关灯操作的右边界防止在扫描到数组末尾时执行j iL导致数组越界访问二分框架left1, rightn在 [1, n] 范围内二分 L利用 L 的单调性将寻找最优解的时间复杂度降低到 O(n log n)答案更新ansmid; rightmid-1记录可行解并向左搜索保证了最终输出的ans是满足条件的“最小” L