企业官网建设流程全解析

P10569 「Daily OI Round 4」Snow

题目描述

下雪了，小 Y 堆了nnn个雪柱排成一排，调皮的小 X 打算推倒这nnn个雪柱，他想在最少的时间内推倒所有雪柱，于是他请你来为他出谋划策。

小 Y 堆的每个雪柱高aia_iai​单位，推倒一个雪柱的时间为该雪柱的高度。小 X 只能从这一排雪柱的两端推雪柱 *，次数不限，小 X 移动的时间可以忽略不计。这样就可以使一个雪柱倒向其他雪柱，从而击倒另一个雪柱（击倒的时间忽略不计），然后发生连锁反应，更加节省时间 **。

设初始的势能为当前手动推倒的雪柱kkk的高度p=akp=a_kp=ak​，则此轮连锁反应中第iii个雪柱倒向第jjj个雪柱时：

• 若p≥ajp\ge a_jp≥aj​，则使第jjj个雪柱也被击倒，并令p←ajp \gets a_jp←aj​。
• 若p<ajp< a_jp<aj​，则第jjj个雪柱的高度减少（不被击倒），终止整个连锁反应，令aj←aj−pa_j \gets a_j-paj​←aj​−p。

请你求出推倒所有雪柱的最短时间。

*：每一次要么从左边推最左边的雪柱，要么从右边推最右边的雪柱。

**：雪柱的倒塌方向取决于推雪柱的方向，如果从左边推，雪柱就会向右依次倒塌（第iii个雪柱倒塌向第i+1i+1i+1个雪柱），反之同理。

输入格式

本题有多组测试数据。

第一行一个整数TTT，表示数据组数。

对于每组数据：

第一行一个整数nnn，表示雪柱的数量。

第二行nnn个整数，分别表示每个雪柱的高度。

输出格式

对于每组数据：输出一行一个整数，表示推倒所有雪柱的最短时间。

输入输出样例 #1

输入 #1

3 5 2 3 1 4 5 6 6 6 6 6 6 6 6 1 1 4 5 1 4

输出 #1

7 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点时间。

【数据范围】

本题采用捆绑测试。

对于全部数据，保证：1≤T≤101 \le T \le 101≤T≤10，1≤n≤1051 \le n \le 10^51≤n≤105，1≤ai≤1091 \le a_i \le 10^91≤ai​≤109。

C++实现

#include<bits/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);cin>>T;assert(T<=10);while(T--){ans=LLONG_MAX;cin>>n;assert(n<=100000);for(i=1;i<=n;i++)cin>>a[i],assert(1<=a[i]&&a[i]<=1e10);for(i=1;i<=n;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(i=n;i>=1;i--){d2[i]=d2[i+1];if(l2[i+1]==0)d2[i]+=a[i],l2[i]=a[i];elseif(l2[i+1]>=a[i])l2[i]=a[i];elsel2[i]=a[i]-l2[i+1],d2[i]+=a[i]-l2[i+1];}for(i=1;i<=n;i++)ans=min(ans,d1[i-1]+d2[i+1]+max(0ll,a[i]-(l1[i-1]+l2[i+1])));cout<<ans<<endl;for(i=0;i<=n+1;i++)d1[i]=d2[i]=l1[i]=l2[i]=0;}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容