【BZOJ】1628 && 1683: [Usaco2007 Demo]City skyline 城市地平线(单调栈)

By | 05月06日
Advertisement

http://www.lydsy.com/JudgeOnline/problem.php?id=1628

http://www.lydsy.com/JudgeOnline/problem.php?id=1683

又是重复的题。。。。

单调栈维护递减,然后相同的话矩形-1

#include <cstdio>  #include <cstring>  #include <cmath>  #include <string>  #include <iostream>  #include <algorithm>  #include <queue>  using namespace std;  #define rep(i, n) for(int i=0; i<(n); ++i)  #define for1(i,a,n) for(int i=(a);i<=(n);++i)  #define for2(i,a,n) for(int i=(a);i<(n);++i)  #define for3(i,a,n) for(int i=(a);i>=(n);--i)  #define for4(i,a,n) for(int i=(a);i>(n);--i)  #define CC(i,a) memset(i,a,sizeof(i))  #define read(a) a=getint()  #define print(a) printf("%d", a)  #define dbg(x) cout << #x << " = " << x << endl  #define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }  inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }  inline const int max(const int &a, const int &b) { return a>b?a:b; }  inline const int min(const int &a, const int &b) { return a<b?a:b; }    const int N=50005;  int n, w, a[N], ans, s[N], top;  int main() {   read(n); read(w);   for1(i, 1, n) { read(w); read(a[i]); }      ans=n;      for1(i, 1, n) {         while(top && s[top]>a[i]) --top;         if(s[top]==a[i]) --ans;         else s[++top]=a[i];     }   print(ans);     return 0;  }

Description

The best part of the day for Farmer John's cows is when the sun sets. They can see the skyline of the distant city. Bessie wonders how many buildings the city has. Write a program that assists the cows in calculating the minimum number of buildings in the city, given a profile of its skyline.

The city in profile is quite dull architecturally, featuring only box-shaped buildings. The skyline of a city on the horizon is somewhere between 1 and W units wide (1 <= W <= 1,000,000) and described using N (1 <= N <= 50,000) successive x and y coordinates (1 <= x <= W, 0 <= y <= 500,000), defining at what point the skyline changes to a certain height.

An example skyline could be:

..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....XXXXXXXXXXXX

and would be encoded as (1,1), (2,2), (5,1), (6,3), (8,1), (11,0), (15,2), (17,3), (20,2), (22,1).

给我们一个由一些矩形构造出来的图,我们需要找到最少矩形的块数来覆盖它 但是这个输入比较奇怪,针对上图,解释如下: 1.1代表在第一列,有高度为1的矩形,矩形由"X"组成.这个矩形有多宽呢,这里并没有告诉你 2.2代表在第二列,有高度为2的矩形,这就间接告诉了你,前面那个矩形有多宽,宽度即2-1 5.1代表在第五列,有高度为1的矩形,这就间接告诉了你,前面那个矩形有多宽,宽度即5-2

This skyline requires a minimum of 6 buildings to form; below is one possible set of six buildings whose could create the skyline above:

.......................... ..........................
.....22.........333....... .....XX.........XXX.......
.111.22.......XX333XX..... .XXX.XX.......5555555.....
X111X22XXX....XX333XXXXXXX 4444444444....5555555XXXXX

..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....666666666666

Input

* Line 1: Two space separated integers: N and W * Lines 2..N+1: Two space separated integers, the x and y coordinate of a point where the skyline changes. The x coordinates are presented in strictly increasing order, and the first x coordinate will always be 1.

Output

* Line 1: The minimum number of buildings to create the described skyline.

Sample Input

10 26
1 1
2 2
5 1
6 3
8 1
11 0
15 2
17 3
20 2
22 1
INPUT DETAILS:
The case mentioned above

Sample Output

6

Similar Posts:

  • bzoj1628: [Usaco2007 Demo]City skyline(单调队列)

    一看就好熟悉好熟悉啊!!!结果还是忘了... 类似这种题呢就用单调队列.例如这道题维护单调递增队列,当下一个比它高,就要新建一个楼,但要是比前一个矮且在前面出现过,那么这个楼就不用再建了. #include<stdio.h> int n,l; int a[60000]; int que[60000]; int cnt; int main() { scanf("%d %d",&n,&l); for(int i=1;i<=n;i++) { int v; s

  • 【BZOJ1645】[Usaco2007 Open]City Horizon 城市地平线【线段树】【矩形面积并】

    [题目链接] /* Pigonometry */ #include <cstdio> #include <algorithm> using namespace std; const int maxn = 40005, maxm = maxn << 1; typedef long long LL; int n, m, pos[maxm], tr[maxm << 2], mxv[maxm << 2]; struct _line { int l, r,

  • how to run demo city bars using sencha architect

    1. create a project using city bars template in sencha architect 2. save your project name as CityBars 3. modify your controll code to: Ext.define('CityBars.controller.Business', { extend: 'Ext.app.Controller', config: { refs: { dataList: '#dataList'

  • BZOJ 3238: [Ahoi2013]差异( 后缀数组 + 单调栈 )

    sa后求出height数组, 答案显然是∑RMQ(height[l],height[r])(1≤l<r≤N), 然后单调栈乱搞O(N)解决. 写了一个晚上, 再这样下去我就得退役了, 呵呵.. ---------------------------------------------------------------- #include<cstdio> #include<cstring> #include<algorithm> #include<stack

  • BZOJ 1113: Poi2008海报PLA(单调栈)

    题目大意:用最少的纸张去覆盖矩形的楼.(此题与楼宽无关) 思路和上述几题差别不大.此题主要是排序后找相同高度.最后用总数减去即可. #include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<string> #include<queue> #include<map> #i

  • bzoj 1660 单调栈

    题意:给定长度为n的序列a1,a2...an,对于每个ai求出它右边第一个大于等于它的位置j,记做ci=j-i-1,求sigma(ci) (1<=1<=n) 单调栈裸上 var i :longint; n,top :longint; ans :int64; z,a :array[0..80010] of longint; begin read(n); for i:=1 to n do read(a[i]); z[1]:=n; top:=1; ans:=0; z[0]:=n+1; for i:=

  • 小结:单调栈 &amp; 单调队列

    概要: 对于维护信息具有单调性的性质或者问题可以转化为具有单调性质的模型的题,我们可以考虑用单调栈或单调队列. 技巧及注意: 技巧很多,只要能将问题转化为单调性问题,就好解决了. 当维护固定长度的单调区间,我们考虑用单调队列,如 [BZOJ]3314: [Usaco2013 Nov]Crowded Cows(单调队列) [BZOJ]1047: [HAOI2007]理想的正方形(单调队列/-二维rmq+树状数组套树状数组)(一维连续的变成二维连续区间) 单调栈维护长度时要进行及时更新,例如: [B

  • bzoj usaco 金组水题题解(2.5)

    bzoj 2197: [Usaco2011 Mar]Tree Decoration 树形dp..f[i]表示处理完以i为根的子树的最小时间. 因为一个点上可以挂无数个,所以在点i上挂东西的单位花费就是i所在子树里的最小单位花费.. 所以每次求f[i]只要使子树里的数量都满足要求就好了..i的祖先还要更多的话随时可以选某个节点多挂一些.. f[i]=sum{f[j]}+mincost[i]*max(need[i]-sum{need[j]},0)..(j是i的儿子,mincost[i]表示子树i里的

  • 在线Demo—城市基础设施管理

    供排水设施管理 网址: http://waterutilitiestemplates.esri.com/WaterUtilitiesOperationsDashboard/index.html 简介 本在线Demo是一个城市供排水基础设施管理系统.系统提供了多种可访问的地图服务,根据需要进行显示控制:地图展现居民用户的服务请求及当前请求的状态:对水表.消防栓等基础设施,对供排水管道进行各种检测.监控:对各种突发事故以图形化的方式表达,同时结合多元信息对管道及设备状态描述,便于分析事故发生的原因:

  • hdu题目分类--第二版

    1001 整数求和 水题 1002 C语言实验题--两个数比较 水题 1003 1.2.3.4.5... 简单题 1004 渊子赛马 排序+贪心的方法归并 1005 Hero In Maze 广度搜索 1006 Redraiment猜想 数论:容斥定理 1007 童年生活二三事 递推题 1008 University 简单hash 1009 目标柏林 简单模拟题 1010 Rails 模拟题(堆栈) 1011 Box of Bricks 简单题 1012 IMMEDIATE DECODABILI

Tags: