P3184 数干草捆题解

涉及一步离散化（其实这么简单根本算不上离散化），以及二分查找的细节处理

内置排序为

O(nlogn)

级别，数据量完全够用

因为想要练二分查找所以就手写了二分

思路很简单：先排序，随后压缩，然后对于每一次询问，找到起始位置的lowerbound，以及最终位置的upperbound并相减

压缩的目的在于，截止压缩过后的数组的第n个位置的时候必然有n个干草捆，等于是采用了类似前缀和的模式

简单代码如下：

CPP

#include<iostream>
#include<algorithm> 
using namespace std;
int n,q;
int a[100005];
int main(){
	cin >> n >> q;
	for(int i=0;i<n;i++){
		cin >> a[i];//压缩
	}
	sort(a,a+n);//排序
	int st,ed;
	int xi,xf;
	for(int i=0;i<q;i++){
		cin >> st >> ed;
		cout << upper_bound(a,a+n,ed)-lower_bound(a,a+n,st) << endl;
	}
	return 0;
}

注：upperbound返回的是第一个大于val的位置索引，而lowerbound返回的是第一个大于等于val的位置索引，在单调不重复序列的查找当中会很没用，但是很显然，并不是所有序列都是单调不重复序列

二分查找的逻辑很简单：求mid，搜左边，搜右边，如果l=r那就返回当前位置

不过对于upper_bound和lower_bound而言，a[mid]=val时，mid大概率不是正确答案，对于upper_bound这一点显然，对于lower_bound而言，正确答案或许在左边更远处

因此进行分治的时候不能把mid本身包含在内

以下为闲的没事版本的代码

CPP

#include<iostream>
#include<algorithm> 
using namespace std;
int n,q;
int a[100005];
int search_low(int val,int l,int r){
	if(l==r){
		return l;
	}
	int mid = (l+r)/2;
	if(a[mid]>=val)return search_low(val,l,mid);
	if(a[mid]<val)return search_low(val,mid+1,r);
}
int search_high(int val,int l,int r){
	if(l==r){
		return l;
	}
	int mid = (l+r)/2;
	if(a[mid]<=val)return search_high(val,mid+1,r);
	if(a[mid]>val)return search_high(val,l,mid);
}
int main(){
	cin >> n >> q;
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	sort(a,a+n);
	int st,ed;
	int xi,xf;
	for(int i=0;i<q;i++){
		cin >> st >> ed;
		xi = search_low(st,0,n);
		xf = search_high(ed,0,n);
		cout << xf-xi << endl;
	}
	return 0;
}

下班收工~

P3184 数干草捆题解

文章操作

相关推荐

评论

P3184 数干草捆题解