【扫描线或树状数组】CSU 1335 高桥和低桥
2024-09-14 06:00:45
http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1335
【题意】
- 给定n座桥的高度,给定m次洪水每次的涨水水位ai和退水水位bi
- 询问有多少座桥被淹的次数大于等于k
- 洪水最开始的水位为1
【思路】
- 每座桥被淹一次是这样的:开始时的水位小于桥的高度,洪水最高点的水位不小于桥的高度,如有一座高度为5的桥,对于数据7 6和7 3被淹的次数都是1(看5在不在(1,7]的区间内)
- 把n座桥排序,每次洪水都有一个区间的桥被淹,问最后每座桥被淹多少次
- 这就是裸的扫描线,或者树状数组区间修改单点查询也可以
【AC】
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll; const int maxn=1e5+;
int a[maxn];
int n,m,k;
int f[maxn];
void init()
{
memset(f,,sizeof(f));
}
int main()
{
int cas=;
while(~scanf("%d%d%d",&n,&m,&k))
{
init();
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
sort(a+,a+n+);
int x,y;
int st=,ed;
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
ed=x;
int pos1=upper_bound(a+,a++n,st)-a;
int pos2=upper_bound(a+,a++n,ed)-a-;
f[pos1]++;
f[pos2+]--;
st=y;
}
int ans=;
int s=;
for(int i=;i<=n;i++)
{
s+=f[i];
if(s>=k) ans++;
}
printf("Case %d: %d\n",++cas,ans);
}
return ;
}
扫描线
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll; const int maxn=1e5+;
int a[maxn];
int tree[maxn];
int n,m,k;
int lowbit(int x)
{
return x&(-x);
}
void add(int k,int x)
{
while(k<=n)
{
tree[k]+=x;
k+=lowbit(k);
}
}
int query(int k)
{
int res=;
while(k)
{
res+=tree[k];
k-=lowbit(k);
}
return res;
}
void init()
{
memset(tree,,sizeof(tree));
}
int main()
{
int cas=;
while(~scanf("%d%d%d",&n,&m,&k))
{
init();
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
sort(a+,a+n+);
int x,y;
int st=,ed;
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
ed=x;
int pos1=upper_bound(a+,a++n,st)-a;
int pos2=upper_bound(a+,a++n,ed)-a-;
add(pos1,);
add(pos2+,-);
st=y;
}
int ans=;
for(int i=;i<=n;i++)
{
if(query(i)>=k)
{
ans++;
}
}
printf("Case %d: %d\n",++cas,ans);
}
return ;
}
树状数组区间修改单点查询
最新文章
- php函数类型
- poj2492_A Bug&#39;s Life_并查集
- hihoCoder#1135
- C#处理猜拳问题(非窗体)
- 【zTree】 zTree使用的 小例子
- 用js实现在加载完成一个页面后自动执行一个方法
- Teradata基础教程中的数据库试验环境脚本
- react 学习与使用记录
- javascript动画效果之透明度(修改版)
- [51nod1329]路径游戏
- 笔记:Struts2 的 JSON 插件
- localStorage和sessionStorage区别(包括同源的定义)
- MySQL 数据库字符集 utf8 和 utf8mb4 的区别
- 移动端键盘密码输入框插件(jquery用于支付密码)
- 关于mac 系统如何通过终端 连接linux服务器 并传文件!
- kubernetes 垃圾回收机制
- ubuntu 终端无法启动:ImportError: cannot import name &#39;sysconfig&#39; from &#39;distutils&#39;
- Delphi对象池MyObjectPool.pas
- RabbitMQ学习以及与Spring的集成(三)
- python @property使用详解