[编程题]丰收
• 热度指数：33869 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
• 算法知识视频讲解

##### 输入描述:
`第一行一个数n(1 <= n <= 105)。第二行n个数ai(1 <= ai <= 1000)，表示从左往右数第i堆有多少苹果第三行一个数m(1 <= m <= 105)，表示有m次询问。第四行m个数qi，表示小易希望知道第qi个苹果属于哪一堆。`

##### 输出描述:
`m行，第i行输出第qi个苹果属于哪一堆。`

```5
2 7 3 4 9
3
1 25 11```

## 输出

```1
5
3```
`````````
import java.util.Arrays;
import java.util.Scanner;

public class apple {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();

int a = 0;
int appleNums[] = new int[n];
for (int i = 0; i < n; i++) {
int input = scanner.nextInt();
appleNums[i] = a + input;
a = appleNums[i];
}

int m = scanner.nextInt();
int searchNums[] = new int[m];
for (int i = 0; i < m; i++) {
searchNums[i] = scanner.nextInt();
}

//二分查找法
for (int i = 0; i < m; i++) {
int index = Arrays.binarySearch(appleNums, searchNums[i]);
if (index>0) {
System.out.println(index+1);
}else{
System.out.println(-index);
}
}
}
}
``````

```

```#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>>appsum(n + 1, { 0,0 });
for (int i = 1; i <= n; ++i) {
cin>>appsum[i].first;
appsum[i] = { appsum[i - 1].first + appsum[i].first,i };
}
int m,q;
cin >> m;
for (int i = 0; i != m; ++i) {
cin >> q;
cout<< lower_bound(appsum.begin(), appsum.end(), make_pair(q,0))->second<< endl;
}
return 0;
}

```

``````#include <iostream>
#include <vector>
using namespace std;

int main()
{
int n;
cin >> n;
vector<int> a(n,0);
for (int i = 0;i != n; ++i)
{
cin >> a[i];
}
int m;
cin >> m;
vector<int> q(m,0);
for (int i = 0; i != m;++i)
{
cin >> q[i];
}
vector<int> sum(n,0);
vector<int> res(m,0);
sum[0] = a[0];
for (int i = 1; i != n;++i)
{
sum[i] = sum[i-1] + a[i];
}
for (int i = 0;i != m; ++i)
{
int fi= 0, la = n-1;
while (fi < la)
{
int mid = (fi + la)>>1;
if (sum[mid] < q[i])
{
fi = mid + 1;
}
else
{
la = mid;
}
}
res[i] = la + 1;
}
for (int i = 0; i != m; ++i)
{
cout << res[i] << endl;
}
return 0;
}
``````

```import bisect

n = int(input())
ai = list(map(int, input().split()))
m = int(input())
qi = list(map(int, input().split()))
for i in range(1, len(ai)):
ai[i] += ai[i - 1]
res = []
for i in qi:
res.append(bisect.bisect_left(ai, i) + 1)
for i in res:
print(i)```

bisect_left能够找到最接近并大于待查找数qi应该插入的位置

```import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[] = new int[n];
a[0] = sc.nextInt();
for(int i=1;i<n;i++){
a[i] = a[i-1]+sc.nextInt();
}
int m = sc.nextInt();
int[] q = new int[m];
for(int i=0;i<m;i++){
q[i] = sc.nextInt();
}
for(int i=0;i<m;i++){
int left=0,right=n-1;
while(left+1!=right){
int mid = (left+right)>>1;
if(q[i]<=a[mid])right=mid;
else left=mid;
}
System.out.println(q[i]>a[left]?right+1:left+1);
}
}
}```

```n = int(input())
ns = list(map(int, input().split()))
m = int(input())
q = list(map(int, input().split()))

for i in range(1, n):
ns[i] += ns[i-1]

for i in q:
l, r =0, n-1
while l < r:
mid = (l +r) >> 1
if ns[mid] < i:
l = mid + 1
else:
r = mid
print(r + 1)
```

```importjava.util.Scanner;
publicclassMain {
//这问题提问次数会很多次，如果每次提问都查询肯定会超时，所以用一个数组nx[i]来存放第i个苹果在第几堆就行，时间复杂度O(n+m+sum)
publicstaticvoidmain(String[] args) {

Scanner sc = newScanner(System.in);
intn = sc.nextInt();
int[] nu = newint[n];
intsum = 0;
for(inti = 0; i < n; i++) {
nu[i] = sc.nextInt();
sum+=nu[i];//一共有多少个苹果
}

intm = sc.nextInt();
int[] mu = newint[m];
for(inti = 0; i < m; i++) {
mu[i] = sc.nextInt();
}

int[] nx = newint[sum+1];
intsu=0;
for(inti = 1, j = 0; i <= sum; i++) {

if(i<=(nu[j]+su)){
//x=j+1（j从0开始）
nx[i]=j+1;//如果第i个苹果小于等于前x推苹果，就赋值为第x推（j从0开始，需加1赋值）
}else
{
nx[i]=++j+1;//否者等于第x+1推苹果，x增加1
su+=nu[j-1];//前x推苹果和
}
}

for(inti = 0; i < m; i++) {
System.out.println(nx[mu[i]]);
}
}```
`}`

public static void main(String [] args)  {
//时间换空间的思想
try (Scanner input = new Scanner(System.in)) {
int n = input.nextInt();
int count = 0; //保存苹果总数,用于创建数组
int[] apple = new int[n+1]; //用数组保存苹果
for (int i = 1; i <= n; i++) {
apple[i] = input.nextInt();
count += apple[i];
}

int[] arr = new int[count+1];
count = 0;
for (int i = 1; i <= n; i++) {
for(int j = count+1; j <= apple[i]+count; j++ ) {
arr[j] = i;
}
count += apple[i];
}
int m = input.nextInt();
for (int i = 0; i < m; i++) {
System.out.println(arr[input.nextInt()]);
}
}
}

```#include <iostream>
using namespace std;
int which_heap(int* heaps, int num, int length);
int main(void){
int n, m, pre = 0, query;
cin>>n;
int *num = new int[n]();
for(int i = 0; i < n; ++i){
cin>>num[i];
num[i] += pre;
pre = num[i];
}
cin>>m;
for(int i = 0; i < m; ++i){
cin>>query;
cout<<which_heap(num, query, n)<<endl;
}
return 0;
}
int which_heap(int* heap, int num, int length){
int left = 0, right = length-1, mid;
while(left+1 < right){
mid = (left+right)/2;
if(heap[mid] == num)
return mid+1;
else if(heap[mid] < num)
left = mid;
else
right = mid;
}
return (num <= heap[left]) ? left+1 : right+1;
} ```
heap[i]表示前i堆之和，这样heap就是一个递增数组，使用二分法，类似二分查找，但此时我们要找的是一个区间而不是数，所以如果while条件是left<right的话可能会变成死循环，我们让right-left=1时退出循环，此时确定区间为[a,b]，确定结果就很简单了，当num<=a时，在第left+1堆，否则在第right+1堆

```n =int(raw_input().strip())
a =map(int, raw_input().strip().split())
m =int(raw_input().strip())
b =map(int, raw_input().strip().split())
fori inrange(1, n):
a[i] +=a[i-1]

fori inb:
l, r =0, n-1
ans =-1
whilel <=r:
mid =(l +r) >> 1
ifa[mid] >=i:
ans =mid
r =mid -1
else:
l =mid +1
printans +1```

```def solution(n,m,apples_sum,target):
l, r = 0, n-1
while l<r:
mid = l+(r-l)//2
if target < apples_sum[mid]:
r = mid
elif target > apples_sum[mid]:
l = mid + 1
else:
return mid+1
return r+1
if __name__ == '__main__':
n = int(input().strip())
apples = list(map(int, input().strip().split()))
m = int(input().strip())
problems = list(map(int, input().strip().split()))
for i in range(1, n):  # 直接在愿数组上累加求和，这是二分法AC的关键
apples[i] += apples[i - 1]
for i in range(m):
target = problems[i]
print(solution(n=n, m=m, apples_sum=apples, target=target))```

```#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int n, m;
int a[N], s[N];

int find(int x) {
int l = 1, r = n;
while(l < r) {
int mid = (l + r) >> 1;
if(s[mid] >= x) r = mid;
else l = mid + 1;
}
return r;
}

int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
s[i] = s[i - 1] + a[i];
}
cin >> m;
while(m--) {
int q;
scanf("%d", &q);
printf("%d\n", find(q));
}
return 0;
}```

JavaScript(Node) 😎题目:网易-丰收（二分查找）
```const readline = require('readline')
input: process.stdin,
ouput: process.stdout
})

let inputArr = []
rl.on('line',line=>{
if(!line) return
inputArr.push(line.trim())
if(inputArr.length === 4){
let n = +inputArr[0]
let m = +inputArr[2]
let appleArr = inputArr[1].split(' ').map(e => +e) // appleArr，表示从左往右数第appleArr[i]堆有多少苹果 -arr
let queryArr =inputArr[3].split(' ').map(e => +e) // queryArr,查询第queryArr[i]个苹果的位置
for (let i = 1; i <=n; i++) {
appleArr[i] += appleArr[i-1]
}
queryArr.forEach(i => {
let res = search(i,appleArr,0,appleArr.length-1)+1
console.log(res)
})
}

})
// 有序的二分查找，递归实现
function search(tag, arr, start, end) {
if (tag <= arr[0]) {
return 0
}
let mid = parseInt((start + end) / 2)
if (end - start <= 1) {
return end
}
if (tag < arr[mid]) {
return search(tag, arr, start, mid)
} else if (tag > arr[mid]) {
return search(tag, arr, mid, end)
} else {
return mid
}
}```

```#include <bits/stdc++.h>
using namespace std;

int n,m;
int a[100001], s[100001], q[100001];

int BS(int i){
int l=0, r=n-1;
while(l<r){
int m = (l+r)>>1;
if(s[m]<q[i])
l = m + 1;
else
r = m;
}
return r+1;
}

int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
if(i==0)
s[i] = a[i];
else
s[i] = s[i-1] + a[i];
}
cin>>m;
for(int i=0;i<m;i++)
cin>>q[i];
for(int i=0;i<m;i++)
cout<<BS(i)<<endl;

return 0;
}```

#include <iostream>
#include <vector>
using namespace std;

int main()
{
int n,a,m,q,tmp=0;
cin>>n;
vector<int> app(n+1);
for(int i=1;i<=n;i++)
{
cin>>app[i];
tmp+=app[i];
}
cin>>m;
vector<int> querry(m+1);
for(int j=1;j<=m;j++)
{
if(n==1) cout<<1<<endl;
else
{
cin>>querry[j];
int l=1,r=n;
while(l<r)
{
int mid=(l+r)/2;
{
r=mid;
}
else
{
l=mid+1;
}
}
cout<<l<<endl;
}
}
return 0;
}

```import java.util.Scanner;
import java.util.Arrays;
//菜鸟一个，利用二分查找AC成功，需要注意的是不要导入全部java包，不然会超时。
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();//输入苹果堆数
int sum = 0;
int[] a = new int[n];//存放每堆苹果数量
for(int i = 0; i < n; i++){
int apple = sc.nextInt();
a[i] = sum + apple;//将每堆苹果以累加的方式存放 形成一个有序不重复数组
sum = a[i];
}
int m = sc.nextInt();//输入询问次数
int[] q = new int[m];
for(int i = 0; i < m; i++){
q[i] = sc.nextInt();//存放每次询问苹果的数量
}
//利用java的binarySearch(object[ ], object key)方法
//返回值：如果key在数组中，则返回搜索值的索引，从0开始计数；
//否则返回-1或者”-“(插入点)。插入点是索引键将要插入数组的那一点，即第一个大于该键的元素索引，从1开始计数。
for(int i = 0; i < m; i++){
int index = Arrays.binarySearch(a, q[i]);
if(index > 0){//索引大于0，表示找到相同元素，因为是从0开始，所以加1
System.out.println(index + 1);
}else{//索引小于0，就是-1或者”-“(插入点)的情况，直接取反
System.out.println(-index);
}
}
}
}```

```import java.util.Scanner;

public class Main{
static class AppleHeap{
int appleNum = 0;
int heapNum = 0;

AppleHeap(int appleNum, int heapNum){
this.appleNum = appleNum;
this.heapNum = heapNum;
}
}
public static void main(String [] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
AppleHeap [] appleHeaps= new AppleHeap[n];
appleHeaps[0] = new AppleHeap(sc.nextInt(),1);
for(int i = 1; i < n; i++){
appleHeaps[i] = new AppleHeap(appleHeaps[ i - 1].appleNum + sc.nextInt(),i + 1);
}
int m = sc.nextInt();
int [] ask = new int[m];
for(int i = 0; i < m; i++){
}

for(int i = 0; i < m; i++){
}

}
//二分查找
private static int find(AppleHeap [] appleHeaps, int num){
int low = 0, high = appleHeaps.length, mid = 0;
while(low <= high){
mid = low + (high - low) / 2;
if(appleHeaps[mid].appleNum < num){
low = mid + 1;
}else if(appleHeaps[mid].appleNum > num){
high = mid - 1;
}else {
return appleHeaps[mid].heapNum;
}
}
if(appleHeaps[mid].appleNum > num){
return appleHeaps[mid].heapNum;
}else {
return appleHeaps[mid].heapNum + 1;
}

}
}```

```

/*

c语言

显然本题直接遍历复杂度达到O(n^2) 对于10^5的数据必然超时

采用维护区间和的线段树 用结构体链表（也可以用数组）实现

将时间复杂度降低到 建树：O(n) 单点查询：O(logn)

拓展：如果用数组实现 空间需要开到4n 证明可以先证明线段树是平衡树（注意：不是查找树）再通过最坏情况是最低一层的节点只有两个 且恰好聚集在最右端 即可证明空间复杂度为O(4n)

*/

#include <stdio.h>

#include <stdlib.h>
#include <string.h>
#define New(a ,i) (a*)malloc(sizeof(a)*i)
#define Cle(a) memset(a ,0 ,sizeof(a))
#define Inv -1
#define MAX 100000

typedef struct node
{
int num;
int key;
struct node* le;
struct node* ri;
}node;

node* root;
int n=0 ,m=0;
int *a=NULL ,*q=NULL;

void input()
{
root=New(node ,1);
root->num=root->key=Inv; root->le=root->ri=NULL;

scanf("%d" ,&n);
a=New(int ,n+1);

for(int i=1 ;i<=n ;++i)
scanf("%d" ,&a[i]);

scanf("%d" ,&m);
q=New(int ,m);

for(int i=0 ;i<m ;++i)
scanf("%d" ,&q[i]);
}

void bulidtree(int l ,int r ,node** ch)
{
node* temp=New(node ,1);
temp->num=Inv; temp->key=Inv; temp->le=temp->ri=NULL;
(*ch)=temp;

if(l == r)
{
(*ch)->num=l; (*ch)->key=a[l];
return;
}

int mid=(l+r)/2;

bulidtree(l ,mid ,&(*ch)->le);
bulidtree(mid+1 ,r ,&(*ch)->ri);
(*ch)->key=(*ch)->le->key+(*ch)->ri->key;
}

int search(int key)
{
node* cur=root;
int sum=0;

while(1)
{
if(cur->le && cur->le->key+sum >= key)
cur=cur->le;
else if(!cur->le)
return cur->num;
else
{
sum+=cur->le->key;
cur=cur->ri;
}
}
}

void ope()
{
for(int i=0 ;i<m-1 ;++i)
printf("%d\n" ,search(q[i]));
printf("%d" ,search(q[m-1]));
}

int main()
{
input();
bulidtree(1 ,n ,&root);
ope();

return 0;
}

```

```"""

"""
import sys
import bisect

if __name__ == "__main__":
# sys.stdin = open('input.txt', 'r')
n = int(input().strip())
a = list(map(int, input().strip().split()))
m = int(input().strip())
q = list(map(int, input().strip().split()))
a_sum = [1]
for i in range(n):
a_sum.append(a_sum[-1] + a[i])
for i in range(m):
ans = bisect.bisect(a_sum, q[i])
print(ans)

```

import java.util.*;
public class Main {
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
TreeMap<Integer,Integer>map=new TreeMap<>();
int sum=0;
for (int i = 0; i <N; i++)
{
sum=sum+sc.nextInt();
map.put(sum, i+1);
}
int M=sc.nextInt();
for (int i = 0; i <M; i++)
{
Map.Entry<Integer,Integer> index = map.ceilingEntry(sc.nextInt());
if(index != null)
{
System.out.println(index.getValue());
}
else
{
System.out.println(1);
}
}
}

}

import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int[] array =new int [N+1];
array[1]=sc.nextInt();
for (int i = 2; i <=N; i++)
array[i]=array[i-1]+sc.nextInt();
int M=sc.nextInt();
for (int i = 0; i <M; i++)
{
int key=sc.nextInt();
int left=1,right=N;
while(left+1!=right){
int mid = (left+right)/2;
if(key<=array[mid])
right=mid;
else left=mid;
}
System.out.println(key<=array[left]?left:right);
}
}
}

import java.util.*;
public class Main {
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int []array=new int [N+1];
int sum=0;
for (int i = 1; i <=N; i++)
{
array[i]=sc.nextInt();
sum+=array[i];
}
int []array_find=new int [sum+1];
int i=1;
int j=1;
while(i<sum)
{
for(int k=0;k<array[j];k++,i++)
{
array_find[i]=j;
}
j++;
}
int M=sc.nextInt();
for (int k = 0; k < M; k++)
System.out.println(array_find[sc.nextInt()]);
}
}

119条回答 17081浏览

# 通过挑战的用户

• 2020-09-27 12:55:55
• 2020-09-27 01:15:42
• 2020-09-26 20:35:30
• 2020-09-26 15:14:18
• 2020-09-24 22:20:16

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题