自动搬运

查看原文

来自洛谷，原作者为

	k3v1n070828 退役的菜鸡

搬运于2025-08-24 21:45:04，当前版本为作者最后更新于2020-04-02 13:51:56，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一道非常简单的贪心题

说下思路：

可以发现填平一个坑的同时，旁边的坑也会连带着被填一些。

∴旁边没填满的那个大坑会连带减少减少a[i]-a[i-1]的深度。

从第一个坑开始用循环：下一个坑是否能被连带着填满，如果不是的话，用ans记录每次的a[i]-a[i-1]。最后输出第一个坑的深度（无法被连带着填满）+ans(后面的坑需要的天数)。

用贪心做代码十分的简洁，唯一需要注意的一点是需要开long long。

话不多说，上代码：

#include<cstdio>
using namespace std;
long long n,a[100005];//十年OI一场空，不开long long见祖宗
long long ans=0;
int main(){
    scanf("%lld",&n);//输入
    for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);//输入
    for(int i=2;i<=n;i++)
		if(a[i]>a[i-1]) ans+=a[i]-a[i-1];//如果旁边坑没被填满，那就增加a[i]-a[i-1]天
    printf("%lld\n",a[1]+ans);//输出
    return 0;
}

蒟蒻的第一篇黄题题解，给蒟蒻点个赞呗

最后，望管理员通过，谢谢！