BZOJ_1628_[Usaco2007_Demo]_City_skyline_(单调栈)
2024-10-16 08:14:04
描述
http://www.lydsy.com/JudgeOnline/problem.php?id=1628
给出\(n\)个距形的影子,问最少是多少个建筑的?(建筑的影子可以重叠).
分析
用单调栈维护一下.
栈内是可能"延续"到当前位置的之前的影子.那么显然比当前位置高的不可能.如果有和当前位置等高的影子,就延续过来,就可以少一个建筑,否则,就向栈里加入当前位置高度的影子.
#include <bits/stdc++.h>
using namespace std; const int maxn=+;
int n,m,top,ans;
int a[maxn],s[maxn];
int main(){
scanf("%d%d",&n,&m); ans=n;
for(int i=;i<=n;i++) scanf("%d",&a[i]), scanf("%d",&a[i]);
for(int i=;i<=n;i++){
while(s[top]>a[i]) top--;
if(s[top]==a[i]) ans--;
else s[++top]=a[i];
}
printf("%d\n",ans);
return ;
}
1628: [Usaco2007 Demo]City skyline
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 432 Solved: 344
[Submit][Status][Discuss]
Description
Input
第一行给出N,W
第二行到第N+1行:每行给出二个整数x,y,输入的x严格递增,并且第一个x总是1
Output
输出一个整数,表示城市中最少包含的建筑物数量
Sample Input
10 26
1 1
2 2
5 1
6 3
8 1
11 0
15 2
17 3
20 2
22 1
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
最新文章
- 分析js中的constructor 和prototype
- 【repost】js中(function(){…})()立即执行函数写法理解
- AngularJS版本下载
- 使用ionic framework创建一个简单的APP
- MySQL连接查询的简单概括+思维导图
- Android判断屏幕开关状态
- FS_11C14温湿度传感器(二)
- Linux命令学习-mpstat
- grails-domain-id 无生成策略,由程序控制
- linux ssh免密码登录设置
- 教你怎么把安卓应用软件放到系统根目录system/app下
- EditorWindow edit ScriptableObject
- ExtJs之DHTML,DOM,EXTJS的事件绑定区别
- GPU总结(1)
- C# 简单的图像边缘提取
- 如何配置svn服务器(通过VisualServer服务器)
- 开源免费天气预报接口API以及全国全部地区代码!!(国家气象局提供)
- SQL Server索引进阶:第七级,过滤的索引
- [Network]Transport Layer
- navicat查询sqlserver数据库编码
热门文章
- 【tarjan】BZOJ 1051:受欢迎的牛
- HTTP 错误 403.14 - Forbidden
- win8双屏敲代码
- LA 4329
- **tomcat简介之web.xml详解
- 2014多校第一场A题 || HDU 4861 Couple doubi
- .net web部署(IIS Express &;&; Nancy Self-Hosting)
- CF 86D Powerful array
- JavaC 编译目录下所有的UTF-8编码的java文件
- Java注解全面解析