NOIP2018 铺设道路
传送门:https://www.luogu.org/problem/P5019
解题报告
序言
三个小时就推了一道题可给我牛x坏了 (▼へ▼メ)
不写写过程都对不起我这三个小时的脑残历程=,=
心路
- 第一阶段: 区间修改,单点询问→线段树or树状数组 + 差分数组 / st表(st表就想想啊根本忘了怎么写了)
-
结果:模板忘了orz (
- 第二阶段: 研究样例,考虑反复找最小值
-
结果:超时+难写→放弃 (额 吸取教训??pa
- 第三阶段:发现了惊天大幂幂!当序列中一个数的差分大于0时,在他自己变为0之前,他前面的数必然会先变为0.
而这个数必然比前面的那个数所需要的操作数多(类似贪心讲义上装AB货物那个?
这个朴素的结论可以用来实现前两阶段的思路了!
结果: 终于over了 o(╥﹏╥)o
最后成品如下↓
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
#define fr(i,n) for(int i = 1; i <= n; i++)
long long n,m,num,minx = INT_MAX,len,ans;
long long a[N],b[N],bj[N];
int main()
{
ios::sync_with_stdio(false);
cin >> n;
fr(i,n){
cin >> a[i];
b[i] = a[i] - a[i - 1];
}
fr(i,n) if(b[i] > 0) ans += b[i];
cout << ans;
return 0;
}
~~对 ,三个小时的比赛我就写了这一道题……(猛男落泪嘤嘤嘤
看题解无脑直接交了积木大赛得了90emmm一看题干妈呀这不是我最开始做铺设道路的思路吗……
猛男落泪x2~~