洛谷 P5019 铺设道路 题解 NOIP2018 提高组 Day1 T1
测评地址:https://www.luogu.org/problemnew/show/P5019
通过时间:2019.3.29
耗时/内存:64ms, 1056KB本蒟蒻想了好久才想到贪心算法的解释
代码来源于@ying_t
经实测发现,最终答案并不用long long
代码如下:
#include<iostream>//比赛时不建议用万能头
using namespace std;
int n,a[100010],i,ans=0;//ans不用long long
int main()
{
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
for(i=2;i<=n;i++)
{
if(a[i]>a[i-1])
ans+=a[i]-a[i-1];
}
ans+=a[1];
cout<<ans;
return 0;
}
贪心算法解释
以测试数据为例
4 3 2 5 3 5
贪心:(5 - 2)+(5 - 3)+ 4 = 9
(5 - 2):
在数列:4 3 2 5 中,5(最大值)对于2(最小值)要多填(5 - 2 = 3)次。
+ 4:
接上文,将多填的3次减去,得到:4 3 2 2 。此时首项(4)最大,即要再填4次。
(5 - 3):
在数列:5 3 5 中,由于3最小,是被两边的5填坑时顺带填掉的。而5(末项)比3多2,即要多填2次。
本蒟蒻瞎猜的