P3184 数干草捆题解

Motbloveut221 · 2025-10-02 14:32:23 · 题解

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

内置排序为O(nlogn)级别，数据量完全够用

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

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

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

简单代码如下：

#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本身包含在内

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

#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 数干草捆题解