CSU 1335: 高桥和低桥 (二分查找,树状数组)
2024-08-27 15:47:52
Description
有个脑筋急转弯是这样的:有距离很近的一高一低两座桥,两次洪水之后高桥被淹了两次,低桥却只被淹了一次,为什么?答案是:因为低桥太低了,第一次洪水退去之后水位依然在低桥之上,所以不算“淹了两次”。举例说明:
假定高桥和低桥的高度分别是5和2,初始水位为1
第一次洪水:水位提高到6(两个桥都被淹),退到2(高桥不再被淹,但低桥仍然被淹)
第二次洪水:水位提高到8(高桥又被淹了),退到3。
没错,文字游戏。关键在于“又”的含义。如果某次洪水退去之后一座桥仍然被淹(即水位不小于桥的高度),那么下次洪水来临水位提高时不能算“又”淹一次。
输入n座桥的高度以及第i次洪水的涨水水位ai和退水水位bi,统计有多少座桥至少被淹了k次。初始水位为1,且每次洪水的涨水水位一定大于上次洪水的退水水位。
Input
输入文件最多包含25组测试数据。每组数据第一行为三个整数n, m, k(1<=n,m,k<=105)。第二行为n个整数hi(2<=hi<=108),即各个桥的高度。以下m行每行包含两个整数ai和bi(1<=bi<ai<=108, ai>bi-1)。输入文件不超过5MB。
Output
对于每组数据,输出至少被淹k次的桥的个数。
Sample Input
2 2 2
2 5
6 2
8 3
5 3 2
2 3 4 5 6
5 3
4 2
5 2
Sample Output
Case 1: 1
Case 2: 3
题目中有一句关键的话:初始水位为1,且每次洪水的涨水水位一定大于上次洪水的退水水位。
解决办法,线段树统计次数+二分法查找优化
AC代码1:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e5+;
int c[N],m,n,k,a[N];
int x[N],y[N];
int lowbit(int k)
{
return k&(-k);
}
void add(int k,int he)//每一项增加一个值
{
while(k>)
{
c[k]+=he;
k-=lowbit(k);
}
}
int search(int x)
{
int tmp=x;
int l=;
int r=n;
int mid;
while(l<r)
{
//printf("%d %d\n",l,r);
mid=((l+r)>>);
if(a[mid]>=tmp) r=mid;
else l=mid+;
}
return r;
}
int Q(int k)
{
int query=;
while(k<=n)
{
query+=c[k];
k+=lowbit(k);
}
return query;
}
int main()
{
int t,from,to,he,kkk=;
while(~scanf("%d%d%d",&n,&m,&k))
{
memset(c,,sizeof(c));
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
sort(a+,a+n+);
for(int i=;i<=m;i++)
{
scanf("%d %d",&x[i],&y[i]);
if(i == )
{
from = i;
to = search(x[i]);
}
else
{
from = search(y[i-]);
to = search(x[i]);
}
add(from,-);
add(to,);
}
int ans = ;
for(int i=;i<=n;i++)
{
int kk =Q(i);
if(kk>=k)
ans = ans+;
}
printf("Case %d: %d\n",kkk++,ans);
}
return ;
}
AC代码二:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdio>
#include<queue>
#define maxn 100000
using namespace std;
int v[maxn];
int f[maxn];
int main()
{
int n,m,qu,i,j,k,sum,a,b,t,da,o=;
int lp;int rp;int *p;
while(~scanf("%d %d %d",&n,&m,&qu))
{
memset(f,,sizeof(f));
a=-,sum=,da=;
for(i=;i<n;i++)
scanf("%d",&v[i]);
sort(v,v+n);
for(i=;i<m;i++)
{
scanf("%d %d",&b,&t);
lp=lower_bound(v,v+n,a+)-v;
rp=lower_bound(v,v+n,b+)-v;
f[lp]+=;
f[rp]-=;
a=t;
}
for(i=;i<n;i++)
{
f[i]+=sum;
sum=f[i];
if(f[i]>=qu)
da++;
//cout<<f[i]<<'\t';
}
printf("Case %d: %d\n",o++,da);
}
return ;
}
最新文章
- Scala元组
- 2016HUAS_ACM暑假集训4B - 递推
- 关于fast cgi和php-fpm的关系
- 1.2 容器-container
- [vijos P1083] 小白逛公园
- python 简单爬虫diy
- BestCoder 1st Anniversary B.Hidden String DFS
- 输出图片的php代码前面不能有空白行
- DataBase 之 常用操作
- Java正则表达式:Pattern类和Matcher类
- mysql主从复制的配置总结
- dedecms标签使用
- [usaco6.1.1Postal Vans]
- jquery easyui combobox 高度自适应
- 【Android Studio安装部署系列】十、Android studio打包发布apk安装包
- Golang数据类型总结及其转换
- JavaScript限制前端页面用户表单输入
- asdasda
- Suffix树,后缀树
- tortoiseSVN 合并代码方法
热门文章
- iconv的安装和使用
- [Todo]Redis &; Mysql可以看的书籍
- Mapreduce报错:java.lang.ClassNotFoundException: Class Mapper not found
- java中class.forName和classLoader加载类的区分
- ajax同步和异步
- c++中的对象复制
- Android Exception 9(requestFeature() must be called before adding content)
- cocos2d-x:初探TestLua
- STL源码剖析(set/map)
- Sybase数据库应用系统调优的五大领域