红酒 公司 网站建设专业建设质量报告

红酒 公司 网站建设,专业建设质量报告,大学生网页设计个人主页,网络营销论文文献小猫排队 时间限制#xff1a;1秒 空间限制#xff1a;256M 网页链接 牛客tracker 牛客tracker 每日一题#xff0c;完成每日打卡#xff0c;即可获得牛币。获得相应数量的牛币#xff0c;能在【牛币兑换中心】#xff0c;换取相应奖品#xff01;助力每日有题…小猫排队时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述世界上最苦恼的事情莫过于排队了特别是排在你前面的猫比你可爱的时候。----《论猫的自我修养》小猫啾啾现在就很苦恼它排在队伍的末尾处等着买酱油前面还有足足n nn只猫咪。但幸运的是小猫啾啾会一种魔法它可以和前面距离它最近且比它可爱可爱值大于啾啾的小猫交换位置被交换的小猫会被传送到啾啾之前的位置。已知啾啾每一分钟开始时可以施展一次魔法而每一分钟过后排在队伍最前面的猫咪就会离开队伍这意味这啾啾会先交换位置然后队伍才开始移动。因为等会还得去买饺子所以啾啾会尽可能地与自身前方比它可爱且未出队的小猫交换位置可以证明交换后必定更快买到酱油现在啾啾想请你帮它计算出它需要多久才能买到酱油离开。输入描述第一行一个整数n nn代表啾啾前方小猫的数量。第二行n nn个用空格隔开的整数代表从队伍最前方到队尾每只小猫的可爱值。第三行一个整数代表啾啾的可爱值。1 ≤ n ≤ 2 ⋅ 1 0 5 1≤n≤2⋅10^51≤n≤2⋅1051 ≤ 可爱值 ≤ 1 0 9 1≤可爱值≤10^91≤可爱值≤109输出描述一行一个整数代表啾啾需要几分钟才能买到酱油离开队伍。示例1输入6 9 7 3 7 6 2 5输出4说明用∗ *∗表示啾啾的位置起始时973762 ∗ 9 7 3 7 6 2 *973762∗无人出队第一分钟时737 ∗ 26 7 3 7 * 2 6737∗269 99已出队第二分钟时3 ∗ 726 3 * 7 2 63∗7269 997 77已出队第三分钟时∗ 726 * 7 2 6∗7269 997 773 33已出队第四分钟时7 772 226 669 997 773 33∗ *∗已出队示例2输入1 5 2输出1说明第一分钟开始的时候啾啾就已经到了队首所以在第一分钟结束时啾啾就会出队。解题思路首先读取前方小猫数量n nn、可爱值数组a aa和啾啾的可爱值x xx遍历数组将所有可爱值大于x xx的小猫的索引压入栈中记录可交换的目标位置栈中按遍历顺序存储索引随后初始化左指针l 0 l0l0、右指针r n rnrn和答案a n s 0 ans0ans0进入循环处理若栈非空且栈顶索引≥ l ≥l≥l说明当前存在可交换的小猫则将r rr更新为该栈顶索引并弹出栈顶调整啾啾的目标位置实现交换之后l ll自增、a n s ansans自增模拟时间流逝和队伍最前方小猫出队该过程通过栈高效维护可交换的索引利用双指针模拟啾啾的交换和出队过程时间复杂度为O ( n ) O(n)O(n)适配n nn达2 e 5 2e52e5的规模无需模拟复杂的交换操作直接通过索引处理精准计算出啾啾买到酱油所需的时间。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefpairll,llpii;constll p1e97;constll N2e510;ll a[N];intmain(){ll n;cinn;for(ll i0;in;i)cina[i];ll x;cinx;stackllstk;for(ll i0;in;i){if(a[i]x)stk.push(i);}ll l0,rn;ll ans0;while(lr){if(stk.size()stk.top()l){rstk.top();stk.pop();}l,ans;}coutansendl;return0;}