[BZOJ1683]&&[Usaco2005 Nov]City skyline 城市地平线

描述 Description

约翰的牛们认为， 太阳升起的那一刻是一天中最美好的， 在那时她们可以看到远方城市模糊的轮廓．显然， 这些轮廓其实是城市里建筑物模糊的影子．

建筑物的影子实在太模糊了， 牛们只好把它们近似地看成若干个边长为 1 单位长度的正方体整齐地叠在一起．城市中的所有建筑物的影子都是标准的矩形．牛们的视野宽 W(l ≤ W ≤ 10⁶ ）个单位长度，不妨把它们接从左到右划分成 W 列，并按 1 到 W 编号．建筑物的轮廓用 N(l ≤ N ≤ 50000）组数给予描述，每组数包含 2 个整数 x, y(l ≤ x ≤ W , 0 ≤ y ≤ 500000），表示从第 x 列开始，建筑物影子的高度变成了 y. 也就是说， 第 x_i 列到第 x_i+l-1 列中每一列建筑物影子的高度都是 yi 个单位长度．

贝茜想知道这座城市里最少有多少幢建筑物，也就是说， 这些影子最少可以由多少个矩形完全覆盖．当然，建筑物的影子可以有重叠．请你写一个程序帮她计算一下． 城市的轮廓可能是这样：

……………………..

…..XX………XXX…….

.XXX.XX…….XXXXXXX…..

XXXXXXXXXX….XXXXXXXXXXXX

于是它可以用 (1,1), (2,2), (5,1), (6,3), (8,1), (11,0), (15,2), (17,3), (20,2), (22,1) 这 10 组数进行描述．不难看出， 这座城市里最少有 6 幢建筑物．以下是这些建筑物的一种分布的可能：

……………………..||……………………..||……………………..

…..22………333…….||…..XX………XXX…….||…..XX………XXX…….

.111.22…….XX333XX…..||.XXX.XX…….5555555…..||.XXX.XX…….XXXXXXX…..

X111X22XXX….XX333XXXXXXX||4444444444….5555555XXXXX||XXXXXXXXXX….666666666666

输入格式 InputFormat

第 1 行：2 个用空格隔开的整数 N 和 W.

第 2 到 N+1 行：每行包括 2 个用空格隔开的整数 x,y，其意义如题中所述．输入中的 x 严格递增，并且第一个数总是 x．

输出格式 OutputFormat

输出一个整数，表示城市中最少包含的建筑物数量．

样例输入 SampleInput

10 40
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10

样例输出 SampleOutput

10

来源 Source

Silver

BZOJ 1683

代码 Code

额这题跟 BZOJ1628 是一模一样的真的没关系么。。。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int f[1000005];
int i,j,t,n,m,l,r,k,z,y,x,ans;
inline int read()
{
    int x=0;char ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
int main()
{
    n=read();m=read();
    ans=0;r=0;f[r]=0;
    for (i=1;i<=n;i++)
    {
         x=read();y=read();
         while (f[r]>y)
         {
            ans++;
            r--;
         }
         if (f[r]==y) continue;
         f[++r]=y;
    }
    while (f[r]>0)
    {
        ans++;
        r--;
    }
    printf("%d\n",ans);
    return 0;
}