SSLZYC 2576 平台

题目大意:
有些平板,每个平板的地址已经选定,任意一平板的两端必需有支柱或者它在另一块平板上。
你会得到各个平板在坐标系中的坐标。每一块平板的坐标都是由它的高度和它的水平方位决定的。每个支柱都距它支撑的平板的边缘半个单位。
算出支持所有平板的支柱的总长度。
这里写图片描述


思路:

直接模拟。

a[i]表示第i列的前a[i]行已经支撑住(即下次搭建只需从地i行开始)的高度
以高度为关键字来排序,然后模拟即可。


代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int a[10001],y[10001],x1[10001],x2[10001];
int n,sum;

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&y[i],&x1[i],&x2[i]);
        x2[i]--;  //不知道为什么要这样,听了dalao WYC 说了之后加上就对了
    } 
    for (int i=1;i<=n-1;i++)
     for (int j=i+1;j<=n;j++)  //冒泡排序
      if (y[i]>y[j])
      {
         swap(y[i],y[j]);
         swap(x1[i],x1[j]);
         swap(x2[i],x2[j]);
      }
    for (int i=1;i<=n;i++)
    {
        sum+=y[i]*2-a[x1[i]]-a[x2[i]];  //记录答案
        for (int j=x1[i];j<=x2[i];j++) a[j]=y[i];  //更改第i列已经支撑的高度
    }
    printf("%d\n",sum);
    return 0;
}

dalao WYC 博客链接

原文地址:https://www.cnblogs.com/hello-tomorrow/p/9313097.html