题解 P2003 【平板】

这道题可以用暴力水过;

我们先按照高度从低到高排序,然后记一个h[]数组;

h[i]代表x轴i这个位置目前最高的一个板;

由于柱子只能撑住边缘的半个单位;

那我们就把坐标上的线改为点;

就是用(x,y)这个点来代表原来(x,y)到(x+1,y)这段板

所以只需要每次放一个木板时,更新下这个木板的从l到r-1这一段的h[]数组;

就好了;

cpp

#include<iostream>
#include<cstdio>
#include<algorithm>
#define II int
#define B bool
#define R register
#define I 123456
using namespace std;

struct node {
    II y,l,r;
}aa[I];

II n,ans;

II h[I];

B maP(node a1,node a2) 
{
    if(a1.y==a2.y) return a1.l<a2.l;
      return a1.y<a2.y;
    // 从低到高排序; 
}

int main()
{
    freopen("1.in","r",stdin);

    scanf("%d",&n);
    for(R II i=1;i<=n;i++)
    {
        scanf("%d%d%d",&aa[i].y,&aa[i].l,&aa[i].r);
        aa[i].r--;
        // 化线段为点; 
    }

    sort(aa+1,aa+n+1,maP);

    for(R II i=1;i<=n;i++)
    {
        ans+=aa[i].y*2-h[aa[i].l]-h[aa[i].r];
        // 放板; 
        for(R II j=aa[i].l;j<=aa[i].r;j++)
        {
            h[j]=max(h[j],aa[i].y);
        }// 更新h[]数组; 
    }

    printf("%d\n",ans);
    exit(0);
}

发表于 2017-09-18 10:42:18 in 题解