【NOIP2013】积木大赛（差分数组，贪心模拟）

题目

原题链接

问题描述

分析

直观思路——贪心模拟：每次都处理最长正整数区段。
以$[2,3,4,1,2]$为例：
$[2,3,4,1,2]?[1,2,3,0,1]?[0,1,2,0,1]?[0,0,1,0,1]?[0,0,0,0,1]?[0,0,0,0,0]$

至少$5$步达到目的。

但如果每次都暴力模拟的话，就会超时，我们可以借助差分数组来简化这个思路。
由$[2,3,4,1,2]$得到的差分数组为$[2,1,1,?3,1]$，其中所有正数的和也就是我们的答案。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const int mod = 1e9+7;
#define fir(i, a, b) for (int i = (a); i <= (b); i++)
ll a[N],b[N],n,ans;
int main(){
    cin>>n;fir(i,1,n){
    cin>>a[i];}b[1]=a[1];ans=a[1];fir(i,2,n){
    b[i]=a[i]-a[i-1];if(b[i]>0)ans+=b[i];}cout<<ans<<endl;
}