洛谷 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
",ans);
    return 0;
}

2018.7.28