首页 > 代码库 > BZOJ1628: [Usaco2007 Demo]City skyline
BZOJ1628: [Usaco2007 Demo]City skyline
1628: [Usaco2007 Demo]City skyline
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 256 Solved: 210
[Submit][Status]
Description
The best part of the day for Farmer John‘s cows is when the sunsets. They can see the skyline of the distant city. Bessie wondershow many buildings the city has. Write a program that assists thecows 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 onlybox-shaped buildings. The skyline of a city on the horizon issomewhere between 1 and W units wide (1 <= W <= 1,000,000) anddescribed using N (1 <= N <= 50,000) successive x and y coordinates(1 <= x <= W, 0 <= y <= 500,000), defining at what point the skylinechanges to a certain height.An example skyline could be:...............................XX.........XXX........XXX.XX.......XXXXXXX.....XXXXXXXXXX....XXXXXXXXXXXXand 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-15.1代表在第五列,有高度为1的矩形,这就间接告诉了你,前面那个矩形有多宽,宽度即5-2This skyline requires a minimum of 6 buildings to form; below isone possible set of six buildings whose could create the skylineabove:.......................... ...............................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
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
HINT
Source
Silver
题解:
cf原题?完全忘了。。。
比较巧妙。首先应该知道 ans<=n,然后考虑ans<n什么情况下会出现?
显然应该是 有两块相同高度的积木,并且这两块积木中间没有比它们低的积木!
那就是单调栈了。
发现OI真是有时候不是看你会不会什么算法,而是你能不能想到某个算法。
代码:
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm>10 11 #include<iostream>12 13 #include<vector>14 15 #include<map>16 17 #include<set>18 19 #include<queue>20 21 #include<string>22 23 #define inf 100000000024 25 #define maxn 50000+10026 27 #define maxm 500+10028 29 #define eps 1e-1030 31 #define ll long long32 33 #define pa pair<int,int>34 35 #define for0(i,n) for(int i=0;i<=(n);i++)36 37 #define for1(i,n) for(int i=1;i<=(n);i++)38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)42 43 using namespace std;44 45 inline int read()46 47 {48 49 int x=0,f=1;char ch=getchar();50 51 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}52 53 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}54 55 return x*f;56 57 }58 int a[maxn],sta[maxn],n,m;59 60 int main()61 62 {63 64 freopen("input.txt","r",stdin);65 66 freopen("output.txt","w",stdout);67 68 n=read();m=read();69 for1(i,n)a[i]=read(),a[i]=read();70 int top=0,ans=n;71 for1(i,n)72 {73 while(a[sta[top]]>a[i])top--;74 if(a[sta[top]]==a[i])ans--;else sta[++top]=i;75 }76 printf("%d\n",ans); 77 78 return 0;79 80 }
BZOJ1628: [Usaco2007 Demo]City skyline
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。