萌新训练3赛后补题(1)二分答案和排序

文章目录题目链接I-遗迹核心的临界容差题目大意解题思路完整代码A-能量任务题目大意解题思路完整代码总结题目链接河南萌新联赛2026第三场I-遗迹核心的临界容差I题题目大意现有n座供能矩阵每一座存在一个灵压值现需要保证相邻两座灵压值之差的绝对值不超过一个阈值x在矩阵之间插入隔离锚断开相邻的两座最多插入k-1个隔离锚求最小的非负整数阈值x解题思路这道题要求最小的阈值x保证最后两数之间的差值大于x不超过k-1也就是最多分成k段所以首先可以先把每两个数之间的差值另存一个数组然后定义一个二分检查函数依次遍历每个数比较大小bool check(ll mid) {ll cnt0; for(ll i0;ib.size();i) { if(midb[i]) cnt; } if(cntk) return false; else return true; }接着在主函数里面把两数之间的差值存进b数组然后用二分查找找最小阈值x分别定义一个最大值和最小值找中间值mid进行以上函数true就把mid赋值给最大值反之把mid1赋值给最小值最后成功找到最小区间ll min00; ll max01e9; while(max0-min01) { ll mid(min0max0)/2; bool xx check(mid); if(xx1) max0mid; else min0mid1; } if(check(min0)) coutmin0; else coutmax0;二分答案基本步骤前提答案区间单调能写出 check( x ),判断 x是否满足条件确定边界lr循环区间未收敛while(lr)取中点:求最小可行解mid(lr)/2向下取整求最大可行解mid(lr1)/2向上取整调用check(mid)判定最小可行可行则 rmid不可行 lmid1最大可行可行则 lmid不可行 rmid-1循环结束lr即为答案完整代码#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second using namespace std; const ll N1e610; ll a[N]; ll n,k; vectorllb; bool check(ll mid) {ll cnt0; for(ll i0;ib.size();i) { if(midb[i]) cnt; } if(cntk) return false; else return true; } int main() { IOS cinnk; k--;//分成k段最多砍k-1刀k自减 vectorll a(n); for(ll i0;in;i){ cina[i]; } if(n1) {cout0; return 0; }//只有一个元素直接返回0 for(int i1;in;i) { b.push_back(abs(a[i]-a[i-1])); } ll min00; ll max01e9; while(max0-min01)//二分模板左闭右开查找满足条件的最小值 { ll mid(min0max0)/2; bool xx check(mid); if(xx1) max0mid;//mid可行尝试找更小的答案 else//不行提高下界 min0mid1; } if(check(min0)) coutmin0; else coutmax0; // coutfixedsetprecision(x) ; return 0; }A-能量任务A题题目大意现有n个任务执行第i个任务前你的当前能量必须不少于hi任务完成后能量变化di变为当前能量di每个任务必须且只能执行一次可以自由决定执行顺序。所有时刻能量都不能为负,已知hidi0因此只要执行前满足门槛执行后就不会立刻变成负数,求完成所有任务所需的最小初始能量解题思路根据给出的样例可以猜测出先执行能量变化为正数的即di0,然后再执行di0的所以先将di分为正负两组di0按hi升序门槛低的先做di0:按hidi降序留的余量多的先做vectorpairll,lla,b; for(int i0;in;i) { ll h,d; cinhd; if(d0) a.push_back({h,d}); else b.push_back({h,d}); } sort(a.begin(),a.end()); sort(b.begin(),b.end(),[](pairint,intp,pairint,intq){ return p.fip.seq.fiq.se; });这里用到了pair 类型1类型2用来封装两个不同类型元素的二元组.first:第一个元素.second第二个元素排序顺序先比较’.first相等再比.second从小到大升序还用到了sortlambdasort(起始迭代器末尾迭代器比较函数)b.begin( ):vector第一个元素位置b.end( ):最后一个元素下一位第三个参数自定义比较规则决定两个元素谁放在前面lambda[]捕获列表空代表不捕获外部变量(pairint,int p,pairint,int q)sort 会任意拿数组里两个元素传入 p、q 做对比return 布尔值返回 true → p 排在 q 前面排好顺序以后定义一个中间值cur去更新能量值分别依次遍历正负两个数组如果curh, ans就加上h-cur然后h赋值给curcur再加上能量变化d遍历结束得到最终结果ansint cur0,ans0; for(auto item:a) {ll hitem.fi,ditem.se; if(curh) ansh-cur,curh; curcurd; } for(autoitem:b) {ll hitem.fi,ditem.se; if(curh) ansh-cur,curh; curcurd; } coutansendl;完整代码#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second using namespace std; const ll N1e610; ll a[N]; void solve() { ll n; cinn; vectorpairll,lla,b; //按d正负分成两组 for(int i0;in;i) { ll h,d; cinhd; if(d0) a.push_back({h,d}); else b.push_back({h,d}); } sort(a.begin(),a.end());//正数增量组按h从小到大排序 sort(b.begin(),b.end(),[](pairint,intp,pairint,intq){ return p.fip.seq.fiq.se; });//负数增量组按 hd 从大到小排序 int cur0,ans0; for(auto item:a)//先处理d≥0组计算需要补充高度 {ll hitem.fi,ditem.se; if(curh) ansh-cur,curh; curcurd; } for(autoitem:b)//再处理d0组 {ll hitem.fi,ditem.se; if(curh) ansh-cur,curh; curcurd; } coutansendl; } int main() { IOS solve(); // coutfixedsetprecision(x) ; return 0; }总结I题主要就是一个二分答案的模版题思路在上方呈现下次遇到二分答案题可以看这道题题解理清思路A题属于一个排序问题先通过猜想或者样例规律大概猜出其前后顺序在一步步实现这道题用到了pair把两个数据打包在一起也就是说需要把两个关联的数绑定在一起时可以优先考虑pair记好排序规则先比firstfirst相等再比second还用到了sort和lambda语法出现lambda一般就是给sort当比较器就是sort自定义排序规则不用另写一个全局函数关键一点是普通 cmp 全局函数拿不到局部变量lambda 可以捕获sort(begin,end,比较器)对[begin,end) 左闭右开区间快速排序lambda 表达式[](参数){逻辑}