首页 > 试题广场 >

丰收

[编程题]丰收

热度指数：34799 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

输入描述:

第一行一个数n(1 <= n <= 10⁵)。
第二行n个数a_i(1 <= a_i<= 1000)，表示从左往右数第i堆有多少苹果
第三行一个数m(1 <= m <= 10⁵)，表示有m次询问。
第四行m个数q_i，表示小易希望知道第q_i个苹果属于哪一堆。

输出描述:

m行，第i行输出第q_i个苹果属于哪一堆。

示例1

输入

输出

1
5
3

算法知识视频讲解

Java

牛客196305255号

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        TreeMap<Integer,Integer> map=new TreeMap<>();
        int sum=0;
        int count=0;
        while(sc.hasNext()){
            int n=sc.nextInt();
            for(int i=0;i<n;i++){
                int a=sc.nextInt();
                count++;
                sum+=a;
                map.put(sum,count);
            }
            int m=sc.nextInt();
            for(int i=0;i<m;i++)
                System.out.println(map.get(map.ceilingKey(sc.nextInt())));
        }
        sc.close();
    }
}

发表于 2021-03-16 16:05:13 回复(0)

Java

chao二

import java.util.Scanner;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr1 = new int[n];
        int[] arr2 = new int[n];
        int pre = 0;
        for (int i = 0; i < n; i++) {
            arr1[i] = sc.nextInt();
            pre += arr1[i];
            arr2[i] = pre;
        }
        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int q = sc.nextInt();
            nadui(arr2, q);
        }
    }
    
    public static void nadui(int[] arr, int index) {
        // 顺序查找超时
        // 改为二分查找
        if (index <= arr[0]) {
            System.out.println(1);
            return;
        }
        int begin = 0;
        int end = arr.length-1;
        int m = (begin + end)/2;
        while (end - begin > 1) {
            if (index > arr[m]) {
                begin = m;
                m = (begin + end)/2;
            }
            else {
                end = m;
                m = (begin + end)/2;
            }
        }
        System.out.println(end+1);
    }
}

发表于 2020-05-31 10:43:31 回复(0)

Java

lil-q

import java.io.*;

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[] line1 = br.readLine().split(" ");
        int m = Integer.parseInt(br.readLine());
        String[] line2 = br.readLine().split(" ");
        int[] ah = new int[n];
        ah[0] = Integer.parseInt(line1[0]);
        for (int i = 1; i < n; i++) {
            ah[i] = Integer.parseInt(line1[i]) + ah[i - 1];
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            int target = Integer.parseInt(line2[i]);
            int l = 0, r = n - 1;
            while (l < r) {
                int mid = l + (r - l) / 2;
                if (ah[mid] < target) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
            sb.append(l + 1).append("\n");
        }
        System.out.print(sb.toString());
    }
}

java 二分查找

发表于 2020-05-11 16:18:35 回复(0)

Java

0x:cafebabe

我使用TreeMap成功之后，发现一个问题，有时候提交能够过，有时候提交会超时，是网的问题吗？好奇怪  import java.util.*;
public class Main{
    public static void main(String[]args){
        int n,m;
        Scanner in=new Scanner(System.in);
        n=in.nextInt();
        int[]storage=new int[n];
        int sum=0;
        TreeMap<Integer,Integer>heap=new TreeMap<>();
        for(int i=0;i<n;i++){
            storage[i]=in.nextInt();
            heap.put(sum+1,i+1);
            sum+=storage[i];
        }
        m=in.nextInt();
        int[]judge=new int[m];
        for(int i=0;i<m;i++){
           judge[i]=in.nextInt();
            if(judge[i]>sum){
                System.out.println(-1);
                continue;
            }
           System.out.println(heap.get(heap.floorKey(judge[i])));
        }
    }
}

发表于 2020-04-06 17:24:56 回复(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

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)

Java

做一个快乐的奋斗逼

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] sum = new int[n];
        for (int i = 0;i < n;i ++){
            if (i == 0)
                sum[i] = scanner.nextInt();
            else
                sum[i] = sum[i - 1] + scanner.nextInt();
        }
        int m = scanner.nextInt();
        for (int i = 0;i < m;i ++){
            System.out.println(erfen(0,n - 1,sum,scanner.nextInt()));
        }
    }
    
    private static int erfen(int start,int end,int[] num,int target){
       while(start < end) {
            int mid = (start + end) >> 1;
            if (num[mid] == target) {
                return mid + 1;
            }else if(num[mid] < target){
                start = mid + 1;
            }else {
                end = mid - 1;
                if (end >= 0) {
                    if (num[end] < target) {
                        return end + 2;
                    }
                }
            }
        }
        return start + 1;
    }
    
}

就是一个二分查找把加号换成位运算就过了

发表于 2019-07-31 14:38:00 回复(0)

Java

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)

Java

木子木泗

public static void main(String[] args) {
        // 开始录入数据
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        int[] temp = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
            sum += a[i];
            temp[i] = sum;
        }
        int m = scanner.nextInt();
        int q[] = new int[m];
        for (int i = 0; i < m; i++) {
            q[i] = scanner.nextInt();
        }
        // 录入数据结束，开始查找
        int start, end, mid;
        boolean flag = false;
        for (int i = 0; i < m; i++) {
            flag = false;
            start = 0; end = n - 1; mid = 0;
            //折半
            while (start <= end) {
                mid = start + (end - start) / 2;
                if (q[i] == temp[mid]) {//恰好找到
                    System.out.println(mid + 1);
                    flag = true;
                    break;
                } else if (q[i] < temp[mid])
                    end = mid - 1;
                else if (q[i] > temp[mid])
                    start = mid + 1;
            }
            if (flag)
                continue;
            System.out.println(1 + Math.max(start, end));
        }
    }

编辑于 2018-08-14 16:19:45 回复(0)