首页 > 试题广场 >

丰收

[编程题]丰收
  • 热度指数：34799 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
又到了丰收的季节，恰逢小易去牛牛的果园里游玩。
牛牛常说他对整个果园的每个地方都了如指掌，小易不太相信，所以他想考考牛牛。
在果园里有N堆苹果，每堆苹果的数量为ai，小易希望知道从左往右数第x个苹果是属于哪一堆的。
牛牛觉得这个问题太简单，所以希望你来替他回答。

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


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

输入

5
2 7 3 4 9
3
1 25 11

输出

1
5
3
算法知识视频讲解
添加回答
——佚名头像 ——佚名 
#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;
}

编辑于 2019-03-13 09:51:07 回复(7)
牛客4407019号头像 牛客4407019号 
#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;
}
发表于 2018-08-21 15:28:49 回复(1)
EnvyEvil头像 EnvyEvil 
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)
用了python的二分查找插入模块bisect
bisect_left能够找到最接近并大于待查找数qi应该插入的位置
编辑于 2019-08-15 11:58:17 回复(0)
Java
Miracle1414头像 Miracle1414

一个简单的二分 

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);
        }
    }
}
编辑于 2019-03-25 22:22:27 回复(3)
鱼头哦头像 鱼头哦
参考改出的简洁python二分解法。。
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)

发表于 2018-09-09 21:57:54 回复(2)
2562589927头像 2562589927 
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]]);
        }
    }
}

发表于 2018-08-24 10:38:17 回复(8)
瑟瑟不想说话头像 瑟瑟不想说话
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()]);
            }
        }
    }
发表于 2018-08-30 12:01:08 回复(2)
小蝌蚪666头像 小蝌蚪666 
#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堆
发表于 2019-07-28 11:22:31 回复(0)
biamgo头像 biamgo 
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

发表于 2018-08-14 17:16:25 回复(1)
pein531头像 pein531
先对苹果堆数组求前缀和，它一定是一个有序的数组，因此可以使用二分查找。对于第i个苹果，只需要找到前缀和数组中第一个大于等于i的元素的位置就可以判断第i个苹果是第几堆了。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strApple = br.readLine().trim().split(" ");
        // 求苹果堆的前缀和数组
        int[] calSum = new int[n];
        for(int i = 0; i < n; i++) {
            int apple = Integer.parseInt(strApple[i]);
            if(i == 0)
                calSum[i] = apple;
            else
                calSum[i] = apple + calSum[i - 1];
        }
        int m = Integer.parseInt(br.readLine().trim());
        String[] queries = br.readLine().trim().split(" ");
        for(int i = 0; i < m; i++){
            int query = Integer.parseInt(queries[i]);
            System.out.println(binarySearch(calSum, query) + 1);
        }
    }
    
    // 找到arr中第一个大于等于num的数的索引
    private static int binarySearch(int[] arr, int num) {
        int left = 0, right = arr.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(arr[mid] < num)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
}

发表于 2021-03-29 21:11:33 回复(0)
Jancydc头像 Jancydc 
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))

发表于 2020-06-15 10:48:51 回复(0)
C/C++
Freyafy头像 Freyafy

前缀和+整数二分

#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;
}
发表于 2020-03-29 22:11:57 回复(0)
萌萌萌哒头像 萌萌萌哒
JavaScript(Node) 😎题目:网易-丰收（二分查找） 
const readline = require('readline')
const rl = readline.createInterface({
    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
    }
}
发表于 2020-02-26 10:43:50 回复(0)
C/C++
nbgao头像 nbgao 
#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;
}

发表于 2019-12-11 10:09:28 回复(0)
C/C++
瓜瓜请多指教头像 瓜瓜请多指教
二分法，AC100%
#include <iostream>
#include <vector>
using namespace std;

int main()
{
   int n,a,m,q,tmp=0;
   cin>>n;
   vector<int> app(n+1);
   vector<long long> add(n+1);
   for(int i=1;i<=n;i++)
   {
       cin>>app[i];
       tmp+=app[i];
       add[i]=tmp;
   }
   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;
           if(add[mid]>=querry[j])
           {
               r=mid;
           }
           else
           {
               l=mid+1;
           }
       }
        cout<<l<<endl;
       }
   }
   return 0;
}
发表于 2019-11-18 16:20:39 回复(0)
Java
惠鸿飞头像 惠鸿飞 
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);
            }
        }
    }
}

发表于 2019-10-29 10:27:48 回复(0)
Java
WZL0x7f头像 WZL0x7f 
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++){
            ask[i] = sc.nextInt();
        }

        for(int i = 0; i < m; i++){
            System.out.println(find(appleHeaps, ask[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;
        }
        
    }
}

发表于 2019-08-10 11:38:31 回复(0)
C/C++
DdddddddA头像 DdddddddA 

	
	

		/*
	


	

		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;
}
发表于 2019-07-07 14:38:57 回复(0)
Python
ElonB头像 ElonB 
"""
构建一个前n项求和的序列，
利用bisect找到应该的插入点
"""
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)

发表于 2019-07-03 11:34:48 回复(0)
改个名字没人认识我头像 改个名字没人认识我

用treemap复杂度有点高：只能ac40%
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);
}
}
}

}
改为二分法查找：还是不行AC30%，看来是要用空间换时间了。
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);
}
}
}
改为最猥琐的狂建数组办法，提交了多次：第一次AC80%，第二次AC30%，第三次通过~~~第四次AC40%，第五次AC30%~~~~***，这是牛客出问题了吧！！！！！看来今天不适合写代码，适合空调屋里含着冰棍吃小龙虾，溜了溜了~~~~

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()]);
    }
}

编辑于 2019-07-01 16:41:17 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 数组 运维工程师 前端工程师 网易 算法工程师 PHP工程师 2019 查找 Java工程师
来自：网易2019秋季校园招...
上传者：小小
难度：
122条回答 22103浏览

热门推荐

通过挑战的用户

查看代码

相关试题

丰收

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号