P11768 破自行车，P11769 歌唱练习

此篇题解有两道题分别是P11768 破自行车 和 P11769 歌唱练习对应的难度分别为洛谷中的普及-和普及/提高小t i p s tipstips点击题目即可跳转到相应网站破自行车难度普及-题目大意天依要从( 0 , 0 ) (0,0)(0,0)走到( a , b ) (a,b)(a,b)每消耗1 11分钟可以从所在位置( x , y ) (x,y)(x,y)移动至( x 1 , y ) (x1,y)(x1,y)( x − 1 , y ) (x-1,y)(x−1,y)( x , y 1 ) (x,y1)(x,y1)或者( x , y − 1 ) (x,y-1)(x,y−1)也就是说从( 0 , 0 ) (0,0)(0,0)走到( a , b ) (a,b)(a,b)一共要走a b abab步消耗a b abab分钟这里拓展一下二维曼哈顿距离公式二维平面两点P ( x 1 , y 1 ) P(x_1,y_1)P(x1​,y1​)、Q ( x 2 , y 2 ) Q(x_2,y_2)Q(x2​,y2​)间距离d ∣ x 1 − x 2 ∣ ∣ y 1 − y 2 ∣ d |x_1 - x_2| |y_1 - y_2|d∣x1​−x2​∣∣y1​−y2​∣现在天依有k kk次机会可以从( x , y ) (x,y)(x,y)瞬间冲到( x l , y ) (xl,y)(xl,y)( x , y l ) (x,yl)(x,yl)( x − l , y ) (x-l,y)(x−l,y)( x , y − l ) (x,y-l)(x,y−l)四个位置中的一个不花费任何时间求最短的时间题目分析情况1 11:情况2 22图中红色箭头为自行车走的黄色箭头是天依步行的大体上一共有两种情况一种是利用自行车接近中点一种是利用自行车走过了往回折返的AC代码暴力模拟includebits/stdc.h#definelllonglong#defineall(x)begin(x),end(x)#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0)usingnamespacestd;inlinevoidsolve(){ll a,b,k,l;cinabkl;while(a0k){a-l;k--;}if(a0){al;k;}while(b0k){b-l;k--;}if(b0){bl;k;}ll t,ans0xffffffffff;if(!k){coutab\n;return;}while(ansllabs(a)llabs(b)k-1){ansllabs(a)llabs(b);tmin(a,b);amax(a,b);bt;a-l;k--;}coutans\n;}intmain(){intT1;cinT;while(T--){solve();}return0;}加入数学优化和快读#includebits/stdc.h#defineintlonglong#defineall(x)begin(x),end(x)#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0)usingnamespacestd;inlineread(){intx0,f1;charchgetchar();while(0ch||ch9){if(ch-)f-1;chgetchar();}while(0chch9){x(x1)(x3)(ch15);chgetchar();}returnx*f;}intT,a,b,k,l,x,y,ans1,ans2;signedmain(){Tread();while(T--){aread();bread();kread();lread();if(l0){coutab\n;continue;}xb/l,ya/l;if(kx)k-x,ans1b-x*l;elseans1b-k*l,k0ll;if(ky)k-y,ans2a-y*l;elseans2a-k*l,k0ll;if(k0ll){if(ans1(l/2)ans2(l/2)ans2ans1){ans2l-ans2;--k;}if(k0ans1(l/2)){ans1l-ans1;--k;}if(k0ans2(l/2)){ans2l-ans2;--k;}}coutans1ans2\n;}return0;}P11769 歌唱练习难度普及/提高题目大意天依有一个n nn天的练习计划规定第i ii天最多练习t i t_iti​个单位时间并且每天的练习时长必须单调不降w i w_iwi​表示每天每单位时间练习对熟悉度提升的效果注意w i 0 w_i0wi​0也是可能发生的要求至多能将她的熟悉度提升多少题目分析这道题用到了贪心算法如果从前往后贪心的话当天的练习时长会影响到第二天的练习时长- 由于贪心的想法当天肯定会努力近可能的达到最大的练习时长但这样的话可能之后的练习时长都比当天的低从而无法保证单调不降- 还有一种可能就是如果当天的练习时长和单调不降的条件制约如果后一天的w i 0 w_i0wi​0 就会干扰结果但是如果从后往前贪心的话一定不会对前一天产生影响故选择从后往前贪心关键代码如下for(intin-1;i1;i--)t[i]min(t[i],t[i1]);当w i 0 w_i0wi​0时的处理方法抵消这时候4 44~6 66天可以不断合并直到合并的权值w i ≥ 0 w_i \ge 0wi​≥0。若第k kk~i ii天合并了那么合并点的权值为∑ j k i w j \sum_{jk}^i w_jjk∑i​wj​合并点的时间取区间内最小时间为t min ⁡ ( t j ( j ∈ [ k , i ] ) ) t \min(t_{j\ (j \in [k,i])})tmin(tj(j∈[k,i])​)我们可以把合并点权值赋值给w i w_iwi​合并点时间赋给t i t_iti​当w i ≥ 0 w_i \ge 0wi​≥0时停止合并关键代码如下while(j01ll*w[i]*t[i]0ll){w[i]w[j];t[i]min(t[i],t[j]);j--;}AC代码#includebits/stdc.h#definelllonglong#defineall(x)begin(x),end(x)usingnamespacestd;inlinevoidsolve(){intn;cinn;vectorllt(n10),w(n10);for(inti1;in;i)cint[i];for(inti1;in;i)cinw[i];for(intin-1;i1;i--)t[i]min(t[i],t[i1]);ll ans0;for(intin;i0;i--){if(w[i]0){ans1ll*w[i]*t[i];}else{intji-1;while(j01ll*w[i]*t[i]0ll){w[i]w[j];t[i]min(t[i],t[j]);j--;}if(1ll*w[i]*t[i]0llj0){ans0;}else{ans1ll*w[i]*t[i];}ij1;}}coutans\n;}intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intT1;// cinT;while(T--){solve();}return0;}小结最近产量有点低还是效率不足差的文章后续都会补上来的滴❤️❤️❤️