洛谷 P1969 积木大赛 解题报告

P1969 积木大赛

题目描述

春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为\(n\)的大厦，大厦可以看成由\(n\)块宽度为1的积木组成，第\(i\)块积木的最终高度需要是\(h_i\)。

在搭建开始之前，没有任何积木（可以看成\(n\)块高度为\(0\)的积木）。接下来每次操作，小朋友们可以选择一段连续区间\([l,r]\)，然后将第\(L\)块到第\(R\)块之间（含第\(L\)块和第\(R\)块）所有积木的高度分别增加1。

小\(M\)是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。

输入输出格式

输入格式：

包含两行，第一行包含一个整数\(n\)，表示大厦的宽度。

第二行包含\(n\)个整数，第\(i\)个整数为\(h_i\)。

输出格式：

建造所需的最少操作数。

说明

对于 \(30\%\)的数据，有 \(1 ≤ n ≤ 10\) ；

对于 \(70\%\)的数据，有 \(1 ≤ n ≤ 1000\) ；

对于 \(100\%\)的数据，有 \(1 ≤ n ≤ 100000,0 ≤ h_i≤ 10000\)。

---

十分神仙的一道题，强行无视了分治和线段树的想法。

然后我打了个看起来很有道理的排序+链表模拟

实际上用了离线贪心的思想，每次先处理掉最高的，贡献的答案即为高度减去和左右两边高的的高度，然后链表删除这个点。

---

Code:

#include <cstdio>

#include <algorithm>

const int N=100010;

int ans,delta,n;

int max(int x,int y){return x>y?x:y;}

std::pair <int,int > dx[N];

int pre[N],suc[N],a[N];

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&dx[i].first);

        a[i]=dx[i].first;

        dx[i].second=i;

        pre[i]=i-1;

        suc[i]=i+1;

    }

    std::sort(dx+1,dx+1+n);

    for(int i=n;i;i--)

    {

        int pree=pre[dx[i].second];

        int succ=suc[dx[i].second];

        ans+=dx[i].first-max(a[pree],a[succ]);

        suc[pree]=succ;

        pre[succ]=pree;

    }

    printf("%d\n",ans);

    return 0;

}

---

2018.7.28