ACM_不知所措的统计员
2024-09-21 02:01:49
Problem Description:
GDUFE-GAME完美结束,按照惯例,会有一篇报道,描述活动期间的盛况,因此相关人员找到负责统计的ASDF,但是ASDF只知道第i个人在S_i时进场,在E_i时离开。为了体现活动的盛大,报道中需要用到某一时刻处在活动现场的人数(这个数当然越大越好),但由于人数太多,ASDF实在是数不过来。如果你帮ASDF完成这个任务,他会请你吃传说中的黯然销魂翅。
Input:
数据包括多个测试实例。
每个测试实例第一行包含一个整数 n (1 ≤ n ≤ 100000) 代表一共有n个人,接下来一行有n个数,代表每个人的进场时间,再接下来一行有n个数代表每个人的离开时间。
时间范围: 0 ~ 100000
Output:
输出某一时刻同时在现场的人数最大值。
Sample Input:
4
1 3 5 7
2 8 6 8
Sample Output:
2
解题思路:差分思想:进场时间点加1,离场时间点减1,然后累加求前缀和即为每个时间点出现的人数,同时更新该时间点在场的最多人数。
AC代码:
#include<bits/stdc++.h>
using namespace std;
int e,n,num,sum,cnt[];//差分数组
int main(){
while(cin>>n){
memset(cnt,,sizeof(cnt));sum=num=;
for(int i=;i<n;++i)cin>>e,++cnt[e];//进场的时间点加1
for(int i=;i<n;++i)cin>>e,--cnt[e];//离场的时间点减1
for(int i=;i<=;++i)sum+=cnt[i],num=max(num,sum);//更新每个时间点的最多人数
cout<<num<<endl;
}
return ;
}
最新文章
- SharePoint 2013 图文开发系列之网站栏
- GoldenGate Studio 12.2.1.1发布
- 数据结构《19》----String容器的三种实现
- 欲哭无泪的@Autowired注入对象为NULL
- CodeForces #100 C 贪心+STL
- CAP理论(转)
- P1351 联合权值
- oracle数据库什么情况下创建索引比较好
- vacabulary1
- Android--WebView控件
- 浅尝key-value数据库(二)——MongoDB的优与劣
- SpringMVC 集成redis
- Python数据类型和数据操作
- springboot - websocket实现及原理
- MAC vim安装gruvbox主题
- 六、Sql Server 基础培训《进度6-更新删除(实际操作)》
- 0-1背包dp|波动数列|2014年蓝桥杯A组10-fishers
- C# asp.net 抓取需要登录的网页内容 抓取asp.net登录验证的网站
- liferay项目经验之BasePortlet
- 对Spark2.2.0文档的学习2-Job Scheduling
热门文章
- 【APUE】线程与信号
- [NPM] npm check to update the dependencies
- 有两个字符串a,b。假设a=";ab";,b=";cd";,判断字符串c=";acbd";是属于a、b的组合。满足组合后a、b的内部顺序均不变。
- Robot Framework操作
- 从程序员角度看ELF | Linux-Programming (转)
- form标签中id和name属性的区别
- DataTables warning requested unknown parameter
- 转:目前为止最全的微信小程序项目实例
- .gitignore 使用入门
- linux系统无法上外网,路由器可以上网,可以ping通路由器,ping不通外网IP