首页 > 试题广场 > 丰收
[编程题]丰收
又到了丰收的季节,恰逢小易去牛牛的果园里游玩。
牛牛常说他对整个果园的每个地方都了如指掌,小易不太相信,所以他想考考牛牛
在果园里有N堆苹果,每堆苹果的数量为ai,小易希望知道从左往右数第x个苹果是属于哪一堆的。
牛牛觉得这个问题太简单,所以希望你来替他回答。

输入描述:
第一行一个数n(1 <= n <= 105)。
第二行n个数ai(1 <= a<= 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 回复(2)
#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)
```
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);
            }
        }
    }
}

```

发表于 2018-08-19 10:02:02 回复(1)

一个简单的二分

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 回复(2)
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 回复(7)
参考改出的简洁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 回复(0)
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)
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)
#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)
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)

/*
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)
"""
构建一个前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)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,a[100001],q[100001],sum[100001];
    cin>>n;
    cin>>a[0];
    sum[0]=a[0];
    for(int i=1;i<n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    cin>>m;
    for(int i=0;i<m;i++)
        cin>>q[i];
    for (int i=0; i < m; i++)
    {
        int f = 0,b = n-1,mid = (f+b)/2;
        while(f != mid)
        {
            if(q[i] < sum[mid])
                b = mid;
            else
                f = mid;
            mid = (f+b)/2;
        }
        if(q[i] <= sum[f])
            cout<<f+1<<endl;
        else
            cout<<b+1<<endl;
    }
    return 0;
}

发表于 2019-06-29 22:07:03 回复(0)
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int n,m;
    while(cin>>n){
        vector<int> a(n,0);
        int i=0,j=0;
        while(n--){
            cin>>a[i];
            if(i>0)
                a[i]+=a[i-1];
            i++;
        }
        cin>>m;
        vector<int> q(m,0);       
        while(m--){
            cin>>q[j++];
        }        
        for(int i=0;i<q.size();i++){
            int pos = lower_bound(a.begin(), a.end(), q[i]) - a.begin();          cout << pos + 1 << endl;
        }        
    }
    return 0;
}


编辑于 2019-03-21 23:28:59 回复(0)
 #include<iostream>;
#include<algorithm>;
using namespace std;
int main () {
    int n,m;
    cin>>n;
    int a;
    int s[100005];
    for(int i=0;i<n;i++) {
        cin>>a;
        s[i] = i==0? a: s[i-1] + a;
    }
    cin>>m;
    for(int i=0;i<m;i++) {
        int q;
        cin>>q;
        int* pos = lower_bound(s, s+n, q);
        cout<<pos-s+1<<endl;
    }
    return 0;
}
发表于 2019-01-19 13:00:19 回复(0)
线性查找效率太低,永远超时。因此,采用二分查找,该题目下的二分查找条件判断比较恶心!
能在短时间完成这一波操作的,才是网易要找的人才吧!
Java:
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int num = sc.nextInt();
    int[] arr = new int[num];
    int sum = 0;
    for (int i = 0; i < num; i++) {
        int t = sc.nextInt();
        sum = sum + t;
        arr[i] = sum;
    }
    int nums = sc.nextInt();
    int[] ar = new int[nums];
    for (int i = 0; i < nums; i++) {
        ar[i] = sc.nextInt();
    }
    for (int i = 0; i < nums; i++) {
        System.out.print(binarySearch(arr, 0, arr.length - 1, ar[i]) + " ");
    }
    }

    public static int binarySearch(int[] a, int start, int end, int val) {
    if (start <= end) {
        int mid = (start + end) / 2;
        if (val <= a[mid]) {
        if (mid - 1 < start)
            return mid + 1;
        else if (val > a[mid - 1])
            return mid + 1;
        else
            return binarySearch(a, start, mid - 1, val);
        } else {
        if (mid + 1 > end)
            return 0;
        else if (val <= a[mid + 1])
            return mid + 2;
        else
            return binarySearch(a, mid + 1, end, val);
        }
    }
    return 0;
    }

发表于 2018-08-21 09:58:50 回复(0)
普通解法可能会超时,使用二分查找来找出苹果在哪一堆,达到空间和时间的平衡

import java.util.*;
public class Main{
    public int getIndex(int[] data, int target){
        int left=0, right=data.length, middle=0;
        while(left <= right){
            middle = left + (right-left)/2;
            if(data[middle] < target)
                left = middle+1;
            else if(data[middle] > target)
                right = middle-1;
            else
                return middle;
        }
        return left;
    }
     
    public void f(){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextLine()){
            int n, m, temp=0;
            n = Integer.parseInt(sc.nextLine());
            int[] data = new int[n+1];
            for(int i=1; i<=n; i++) {
                temp += sc.nextInt();
                data[i] = temp;
            }
            sc.nextLine();
            m = Integer.parseInt(sc.nextLine());
            for(int i=1; i<=m; i++){
                temp = sc.nextInt();
                System.out.println(getIndex(data, temp));
            }
            sc.nextLine();
        }
    }
     
    public static void main(String[] args){
        new Main().f();
    }
}


发表于 2018-09-04 16:30:36 回复(1)
/*强大的STL*/
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,m,t;
ll a[100005];
ll q;
int main()
{
    cin>>n;
    a[0]=0;
    for(int i=1;i<=n;i++){
        cin>>t;
        a[i]=a[i-1]+t;
    }
    cin>>m;
    for(int i=0;i<m;i++){
        cin>>q;
        int loc=lower_bound(a+1,a+n+1,q)-a;
        cout<<loc<<endl;
    }
    return 0;
}

发表于 2018-08-15 19:22:10 回复(0)

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] total=new int[n];
        int sum=0;
        for(int i=0;i<n;i++) {
            sum+=sc.nextInt();
            total[i]=sum;
        }
        int m=sc.nextInt();
        int q=0;
        for(int i=0;i<m;i++) {
            q=sc.nextInt();
            int start=0,end=n-1,mid=0;
            while(start+1!=end) {
                mid=(start+end)/2;
                if(q>total[mid]) {
                    start=mid;
                }else {
                    end=mid;
                }                
            }
            System.out.println(q>total[start]?end+1:start+1);
        }        
    }    
}

发表于 2019-08-17 14:23:55 回复(0)