NOIP2018DAY1铺设道路(贪心)

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~~

上一篇:thinkphp中的类库与引用import引入机制


下一篇:AtCoder Grand Contest 038E - Gachapon