题目内容

P2003

大意:给定n个平板,支柱可以互相搭,求支柱花费

解题思路

第一眼看到的时候我都惊了,一道普及-的题居然会有线段树的标签。

先不管,分析思路:

首先,上面的平板大概率要搭在下面的平板上,所以处理的时候一定要从下往上处理。这里可以使用结构体排序。

然后,为了得到当前板子需要的支柱高度,就需要搞清楚下面有没有板子,板子的高度是多少,所以定义一数组h,储存坐标[i,i+1]区间内的最高值。

接下来搞定了支柱高度,就要刷新当前范围内的h了,但是很明显需要将一片区间赋值为当前的高度。所以可以使用线段树进行区间赋值。但一看数据范围,发现所有坐标不大于1e4,所以n方暴力完全可以跑过去。

代码:

#include <cstdio>
#include <algorithm>
using std::sort;

int h[10005],n;//表示[i,i+1]板子的最高高度
struct pad
{
    int y,x1,x2;
}p[105];

bool cmp(pad a,pad b)
{
    return a.y<b.y;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d %d %d",&p[i].y,&p[i].x1,&p[i].x2);
    sort(p+1,p+1+n,cmp);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int x1=p[i].x1,x2=p[i].x2,y=p[i].y;
        ans+=(y-h[x1]+y-h[x2-1]);
        for(int j=x1;j<x2;j++)
            h[j]=y;
    }
    printf("%d\n",ans);
    return 0;
}
最后修改日期:2020年2月8日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。