【PAT甲级真题】- Shopping in Mars (25)

题目来源Shopping in Mars (25)题目描述点击链接自行查看注意点输出时按照区间左端点从小到大输出思路简介简单的滑动窗口我做了一个小处理因为题目实际上要求找的是大于等于目标值的区间所以移动左指针的条件写成lrsumm这样我认为有两个好处首先使得lr的情况可以被判断到其次遍历完成后l-1的位置开始的区间和必定是大于等于m的可以直接取l-1不用特判l0的情况维护一个最小差值和答案数组当最小插值被更新时清空数组最后也不用排序因为左端点本来就是从小到大存的我提到了清空数组的操作虽然vector.clear()的开销是O(n)但是实际上如果符合条件的区间多那么清空次数应该会相应减少清空次数多那么每次清空的区间数应该不多。平均下来总时间应该还是O(n)的量级具体时间复杂度不会算。。但反正清空不会爆时间要是有大佬会算可以评论区展示一波让博主也学习一下遇到的问题无一遍过代码/** * https://www.nowcoder.com/pat/5/problem/4083 * 滑动窗口 */#includebits/stdc.husingnamespacestd;typedeflonglongll;constintN1e510;ll v[N];voidsolve(){ll n,m;cinnm;for(inti0;in;i)cinv[i];vectorpairint,intres;ll l0,r0,sum0,mi1e810;for(ll r0;rn;r){sumv[r];if(summ)continue;while(lrsumm){sum-v[l];l;}if(sumv[l-1]-mmi){misumv[l-1]-m;res.clear();pairint,inta{l-1,r};res.emplace_back(a);}elseif(sumv[l-1]-mmi){pairint,inta{l-1,r};res.emplace_back(a);}}intlenres.size();//coutmi\n;for(inti0;ilen;i)coutres[i].first1-res[i].second1\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//fstream in(in.txt,ios::in);cin.rdbuf(in.rdbuf());intT1;//cinT;while(T--){solve();}return0;}