洛谷 P3184 [USACO16DEC]Counting Haybales数草垛
题目描述
Farmer John has just arranged his NN haybales (1 \leq N \leq 100,0001≤N≤100,000 ) at various points along the one-dimensional road running across his farm. To make sure they are spaced out appropriately, please help him answer QQ queries (1 \leq Q \leq 100,0001≤Q≤100,000 ), each asking for the number of haybales within a specific interval along the road.
农夫John在一条穿过他的农场的路上(直线)放了N个干草垛(1<=N<=100,000),每个干草垛都在不同的点上。为了让每个干草垛之间都隔着一定的距离,请你回答农夫John的Q个问题(1<=Q<=100,000),每个问题都会给出一个范围,询问在这个范围内有多少个干草垛。
(其实就是有一条数轴上有N个不重复的点,再问Q个问题,每个问题是给出一个范围,问此范围内有多少个点?)
(在给出范围的边界上也算)
输入输出格式
输入格式:
The first line contains NN and QQ .
The next line contains NN distinct integers, each in the range 0 \ldots 1,000,000,0000…1,000,000,000 , indicating that there is a haybale at each of those locations.
Each of the next QQ lines contains two integers AA and BB (0 \leq A \leq B \leq 1,000,000,0000≤A≤B≤1,000,000,000 ) giving a query for the number of haybales between AA and BB , inclusive.
第一行包括N和Q
第二行有N个数字,每个数字的范围在0~1,000,000,000,表示此位置有一个干草垛。
接下来的Q行,每行包括两个数字,A和B(0<=A<=B<=1,000,000,000)表示每个询问的范围
输出格式:
You should write QQ lines of output. For each query, output the number of haybales in its respective interval.
总共Q行,每行输出此范围内的干草垛数量
输入输出样例
说明
感谢@2014nhc 提供翻译
思路:先排序,再二分,然后下标减一下就好了。
upper_bound 找第一个大于查找值的元素。
lower_bound 找第一个大于等于查找值的元素。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 100010
using namespace std;
int n,m,q,tot;
int pos[MAXN],hash[MAXN];
int main(){
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++) scanf("%d",&pos[i]);
sort(pos+,pos++n);
for(int i=;i<=q;i++){
int x,y;scanf("%d%d",&x,&y);
cout<<upper_bound(pos+,pos+n+,y)-lower_bound(pos+,pos+n+,x)<<endl;
}
}
最新文章
- [转]CTO、技术总监、首席架构师的区别
- TestNG 三 测试方法
- CSS3-border-radius的兼容写法大全
- Netfilter深度解剖
- 自动化:Appium运行成功,取得一个小的胜利
- Java IO (5) - 总结
- Linux学习之挂载
- jquery 调用wcf 的SOA架构,将三层架构运用到SOA的架构中来(第四天)
- mavean的依赖传递和排除依赖
- guava-19.0和google-collections-1.0 的 ImmutableSet 类冲突
- app模块设计
- n2n的编译和运行、配置
- .NET EntityFrameworkCore.DbUpdateException 错误
- linux内核中链表代码分析---list.h头文件分析(一)【转】
- Jenkins 总结
- SQL语句的执行过程
- ubuntu svn二进制文件
- Java基本类型与运算
- java语言导学(5版)--第12章并发之二
- python学习笔记——正则表达式regex