青岛今日头条新闻消息_整套网站设计_杭州做网站的公司排行_百度官方平台

性价比的一题！！！

D. C05.L08.贪心算法入门（一）.课堂练习4.危险的实验(NHOI2015初中)

• 传统题1000ms256MiB

题目描述

小明最近在上化学课，他需要使用到 n 种化学物质来进行他的实验。在做实验的时候，他需要将所有化学物质放在桌面上，按次序排成一条直线。

然而每一种化学物质都是危险品，对于第 i 个化学物质，如果有另外一个化学物质距离它的距离小于 a_iai​，那么就会发生爆炸。

小明想知道如果要安全的完成他的实验，桌子最短可以多短。

输入格式

第一行一个整数 n ，表示化学物质的个数。

第二行有 n 个整数，第 i 个整数 a_iai​ 表示第 i 个化学物质必须与其他化学物质保持的距离。

数据范围

20% 的数据 , 1 <= n <= 20

50% 的数据 , 1 <= n<= 100000

100% 的数据 , 1 <= n <= 1000000 , 1 <= a_iai​ <= 100000

输出格式

一个整数，表示能够让小明安全完成实验的桌子最小长度。

注意：物品要安原来的次序摆放。

样例

输入数据 1

3
3 1 2

Copy

输出数据 1

5

代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[10000001],o=0;
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<n;i++){o=o+max(a[i],a[i+1]);}cout<<o;return 0;
}

谢谢观看！！！！