P76035 找到所属箱子 — 题解

专题： 二分
适用题目： 新生 OJ 本地题包中的 P76035，不要直接用于外站同名题。

解题思路

箱子前缀和严格递增；寻找第一个大于等于全局编号 x 的前缀位置。

复杂度

预处理 $O(n)$，单次查询 $O(\log n)$。

易错点

二分答案是箱子编号，输出使用 1 起始下标。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int lower_bound_ll(const long long *a,int n,long long x){
    int l=0,r=n;
    while(l<r){int mid=l+(r-l)/2;if(a[mid]<x)l=mid+1;else r=mid;}
    return l;
}
int main(void) {
    int n,q;scanf("%d",&n);long long *pre=malloc(n*sizeof(long long));
    long long sum=0;
    for(int i=0;i<n;i++){long long x;scanf("%lld",&x);sum+=x;pre[i]=sum;}
    scanf("%d",&q);
    while(q--){long long x;scanf("%lld",&x);printf("%d\n",lower_bound_ll(pre,n,x)+1);}
    free(pre);return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n;
    vector<ll>pre(n);
    ll sm=0;
    for(auto &x:pre){
        ll y;
        cin>>y;
        sm+=y;
        x=sm;
    }
    cin>>q;
    while(q--){
        ll x;
        cin>>x;
        cout<<lower_bound(pre.begin(),pre.end(),x)-pre.begin()+1<<nl;
    }
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。