P10569 「Daily OI Round 4」Snow题目描述下雪了小 Y 堆了nnn个雪柱排成一排调皮的小 X 打算推倒这nnn个雪柱他想在最少的时间内推倒所有雪柱于是他请你来为他出谋划策。小 Y 堆的每个雪柱高aia_iai​单位推倒一个雪柱的时间为该雪柱的高度。小 X 只能从这一排雪柱的两端推雪柱 *次数不限小 X 移动的时间可以忽略不计。这样就可以使一个雪柱倒向其他雪柱从而击倒另一个雪柱击倒的时间忽略不计然后发生连锁反应更加节省时间 **。设初始的势能为当前手动推倒的雪柱kkk的高度pakpa_kpak​则此轮连锁反应中第iii个雪柱倒向第jjj个雪柱时若p≥ajp\ge a_jp≥aj​则使第jjj个雪柱也被击倒并令p←ajp \gets a_jp←aj​。若pajp a_jpaj​则第jjj个雪柱的高度减少不被击倒终止整个连锁反应令aj←aj−pa_j \gets a_j-paj​←aj​−p。请你求出推倒所有雪柱的最短时间。*每一次要么从左边推最左边的雪柱要么从右边推最右边的雪柱。**雪柱的倒塌方向取决于推雪柱的方向如果从左边推雪柱就会向右依次倒塌第iii个雪柱倒塌向第i1i1i1个雪柱反之同理。输入格式本题有多组测试数据。第一行一个整数TTT表示数据组数。对于每组数据第一行一个整数nnn表示雪柱的数量。第二行nnn个整数分别表示每个雪柱的高度。输出格式对于每组数据输出一行一个整数表示推倒所有雪柱的最短时间。输入输出样例 #1输入 #13 5 2 3 1 4 5 6 6 6 6 6 6 6 6 1 1 4 5 1 4输出 #17 6 8说明/提示【样例解释】对于第一组数据第一次从左边推耗费222点时间使得555个雪柱 的高度分别变为0,1,1,4,50,1,1,4,50,1,1,4,5。第二次从右边推耗费555点时间使得所有雪柱都被击倒。共耗费777点时间。对于第二组数据从左边或者右边都可以一次性推完共耗费666点时间。对于第三组数据第一次从右边推耗费444点时间使得666个雪柱的高度分别变为1,1,4,4,0,01,1,4,4,0,01,1,4,4,0,0。第二次从右边推耗费444点时间使得所有雪柱都被击倒。共耗费888点时间。【数据范围】本题采用捆绑测试。Subtask\text{Subtask}Subtask分值n≤n \len≤00010101020202011115151510010010022225252510001000100033350505010510^5105对于全部数据保证1≤T≤101 \le T \le 101≤T≤101≤n≤1051 \le n \le 10^51≤n≤1051≤ai≤1091 \le a_i \le 10^91≤ai​≤109。C实现#includebits/stdc.h#definelllonglong#defineN100005usingnamespacestd;ll T,n,i,a[N],ans,d1[N],d2[N],l1[N],l2[N];intmain(){ios::sync_with_stdio(false);cinT;assert(T10);while(T--){ansLLONG_MAX;cinn;assert(n100000);for(i1;in;i)cina[i],assert(1a[i]a[i]1e10);for(i1;in;i){d1[i]d1[i-1];if(l1[i-1]0)d1[i]a[i],l1[i]a[i];elseif(l1[i-1]a[i])l1[i]a[i];elsel1[i]a[i]-l1[i-1],d1[i]a[i]-l1[i-1];}for(in;i1;i--){d2[i]d2[i1];if(l2[i1]0)d2[i]a[i],l2[i]a[i];elseif(l2[i1]a[i])l2[i]a[i];elsel2[i]a[i]-l2[i1],d2[i]a[i]-l2[i1];}for(i1;in;i)ansmin(ans,d1[i-1]d2[i1]max(0ll,a[i]-(l1[i-1]l2[i1])));coutansendl;for(i0;in1;i)d1[i]d2[i]l1[i]l2[i]0;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容