题解 P2003 【平板】
wuzhoupei
2017-09-18 10:42:18
这道题可以用暴力水过；
我们先按照高度从低到高排序，然后记一个h[]数组；
h[i]代表x轴i这个位置目前最高的一个板；
由于柱子只能撑住边缘的半个单位；
那我们就把坐标上的线改为点；
就是用(x，y)这个点来代表原来(x，y)到(x+1，y)这段板
所以只需要每次放一个木板时，更新下这个木板的从l到r-1这一段的h[]数组；
就好了；
cpp
```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);
}
```