自动搬运

查看原文

来自洛谷，原作者为

	baokun 万物有界，爱恨无由。but蓝勾被夺

搬运于2025-08-24 22:59:15，当前版本为作者最后更新于2024-06-07 12:33:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Part 1 前言

本来想打这次基础赛的，有事没参与，这就是 T4 绿题（建议降一下）。

Part 2 题意

题目传送门

小 X 要推倒小 Y 的 $n$ 个雪柱，这些雪柱排成一排，每个雪柱都有各自的高度，小 X 只能从最左边或最右边推雪柱，并引发连锁反应。推倒第 $i$ 个雪柱要花费 $a_i$ 的时间，求推倒所有雪柱子花费的最小时间。

Part 3思路

很明显，要运用贪心来解决这个问题：

因为只能从左或从右推，所以枚举一个 $i$，求两个方向推到 $i$ 所使用的时间以及从两端推到 $i$ 后有多大惯性，足不足够把 $i$ 推倒。若是两边的势能能将 $i$ 推倒，则结果为两边推到这的时间之和，否则就再加上 $a_i$ 剩余的高度。对于每次得到的答案，取最小值即可。

这么说可能有点抽象，那么咱画个图（更抽象了）：

黄色箭头表示左右推倒的进度（ $i$ 的位置不唯一，所以没有具体下标）。

你以为结束了？不，让我们看看数据范围：

对于全部数据，保证： $1 ≤ T ≤ 10,1 ≤ n ≤ 10^5,1 ≤ a_i ≤ 10^{10}$。

so: 不开long long 见祖宗

Part 4 代码（有注释）

#include<bits/stdc++.h>
#define ll long long
#define N 100005 
using namespace std;
ll T,n,i,a[N],ans,d1[N],d2[N],l1[N],l2[N];
int main(){
	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]; // 如果前一个雪柱被完全推倒，则当前雪柱独立推倒
			else if(l1[i-1]>=a[i]) l1[i]=a[i]; // 如果前一个雪柱未倒下且足够的势能推倒当前雪柱
			else l1[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]; // 如果后一个雪柱被完全推倒，则当前雪柱独立推倒
			else if(l2[i+1]>=a[i]) l2[i]=a[i]; // 如果后一个雪柱未倒下且足够的势能推倒当前雪柱
			else l2[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;
	}
	return 0; // 好习惯 
}

Part 5 后记

感谢 Acoipp 如有问题请联系我删帖。