#C240927A. [NOIP2018 提高组] 铺设道路

标签（Label）

贪心
观察+分析

网址（Website）

[NOIP2018 提高组] 铺设道路 - 洛谷

题解（Solution）

$\qquad$这是一道离谱贪心题目。

$\qquad$直接暴力搜，如果出现 $a[i]>a[i-1]$ 的情况，说明 $a[i-1]$ 在填充的时候就可以顺便帮 $a[i]$ 填充小于等于 $a[i-1]$ 的那一部分，那么只需要填充剩下的 $a[i]-a[i-1]$ 的那一部分就好了。

$\qquad$为什么可以这么思考呢？假设最开始的时候填充了 $a[i]$ ，那么这个 $a[i]$ 可以一直填到下一个比 $a[i]$ 小的位置为止。（例如数组 $1,4,2,5,4,6,3$ ，在填到 $4$ 的时候就可以顺便把后面的数的小于等于 $2$ 的部分全部填充，剩下的 $2$ 次填充由于被后面的 $2$ 阻挡，只能用于自己的填充）可以理解为，当前点 $a[i]$ 会阻拦所有 $\ge a[i]$ 的填充，所以才导致出现 $a[i]>a[i-1]$ 时需要花费额外的 $a[i]-a[i-1]$ 去填充被 $a[i-1]$ 挡住的部分。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2012345;
bool ST;

int n,ans,a[N];

bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	cin>>n;int Tim = clock();
	For(i,1,n) cin>>a[i];
	For(i,2,n) if(a[i]>a[i-1]) ans += a[i] - a[i-1];
	cout<<ans+a[1]<<'\n';
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}