二分法-004

傷城~ 2023-07-12 08:55 4阅读 0赞

# 忘了题目！！！ #

import java.util.Scanner;
    
    public class 二分法2 {
        
        //查找a[]数组中
        static int n,m;
        static int a[]=new int[100002];
        public static boolean find(int top){
        
            int num=1;
            int cur=0;
            for (int i = 0; i <n ; i++) {
        
                if (cur+a[i]<=top) cur+=a[i];
                else {
        
                    num++;
                    cur=a[i];
                }
            }
            return (num<=m);
        }
        public static void main(String[] args) {
        
            Scanner scanner=new Scanner(System.in);
            n=scanner.nextInt();
            m=scanner.nextInt();
            int sum=0;
            int ma=0;
            while (true){
        
                for (int i = 0; i <n ; i++) {
        
                    a[i]= scanner.nextInt();
                    sum+=a[i];
                    ma=Math.max(ma,a[i]);
                }
                int low=ma,high=sum,mid;
                while (low!=high){
        
                    mid=(low+high)/2;
                    if (find(mid)) high=mid;
                    else low=mid+1;
                }
                System.out.print(low);
            }
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，4人围观）

还没有评论，来说两句吧...

相关阅读

相关二分法排序_二分法排序算法

\includeintfun(inta\[\],intn,intkey)\{intlow,mid,high;//low、mid、high是三个索引分别指向数组的下标low=0;

谁践踏了优雅/ 2023年09月24日 03:39/ 0 赞/ 60 阅读

相关二分法-004

忘了题目！！！ import java.util.Scanner; public class 二分法2 { /

傷城~/ 2023年07月12日 08:55/ 0 赞/ 5 阅读

相关二分法查找

package com.abstractdatatype.search; /二分法查找/ public class BinarySearch {

亦凉/ 2022年08月13日 15:54/ 0 赞/ 211 阅读

相关 Mod （二分法）

Kim刚刚学会C语言中的取模运算（mod）。他想要研究一下一个数字A模上一系列数后的结果是多少。帮他写个程序验证一下。 Input 第一行一个整数T代表数据组数。接下来

我不是女神ヾ/ 2022年06月09日 04:19/ 0 赞/ 185 阅读

相关二分法 -算法

二分法查找，这个算法要求数据要是有序的。比如有这样的问题：找出一个数组中，两个数的和小于等于15，然后输出他们，否则就单独输出较大的数。 BinarySearc

╰半夏微凉°/ 2022年06月09日 01:13/ 0 赞/ 186 阅读

相关二分法查找

二分法查找当线性表中数据元素是按大小排列存放时，可以改进顺序查找算法，以得到更高效率的新算法——二分法 (折半查找)。 ![这里写图片描述][SouthEast]

电玩女神/ 2021年09月14日 15:00/ 0 赞/ 472 阅读

相关 java 二分法

public class Test4 \{ public int binarySearch(int\[\] items, int value)\{

末蓝、/ 2021年09月11日 07:04/ 0 赞/ 301 阅读

相关二分法查找

一参考文档 [https://zhangjia.io/959.html][https_zhangjia.io_959.html] [https://zhidao.baid

本是古典何须时尚/ 2021年07月25日 01:10/ 0 赞/ 438 阅读

相关 js 二分法

二分法前提：有序，且从小到大有序结束条件当leftIndex>rightIndex时结束代码示例： <html>

心已赠人/ 2021年07月24日 14:33/ 0 赞/ 534 阅读

相关二分法（java）

最先接触到算法神奇之处的就是二分法，所以打算动手写一下，并整理思路代码

灰太狼/ 2021年01月24日 18:19/ 0 赞/ 550 阅读