二分
本文最后更新于 633 天前,其中的信息可能已经有所发展或是发生改变。

二分

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 [

这是关于二分的三道题,二分查找算法的原理就是,分区间查找,定义一个中间值,与原数进行比较,定位小区间大区间,再在这个区间内不断二分

定位区间,二分区间,定位区间,二分区间。

(1.)分巧克力

儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 �N 块巧克力,其中第 �i 块是 ��×��H**i×W**i 的方格组成的长方形。为了公平起见,

小明需要从这 �N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足:

  1. 形状是正方形,边长是整数;

  2. 大小相同;

例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大,你能帮小明计算出最大的边长是多少么?


public class Main {
     public static void main(String[] args) {
         Scanner scan = new Scanner(System.in);
         //在此输入您的代码...
         int N=scan.nextInt();
         int K=scan.nextInt();
         int number[][]=new int [N][2];
         for(int i=0;i<N;i++){
           number[i][0]=scan.nextInt();
           number[i][1]=scan.nextInt();
        }
         long l=1;//区间左端点
         long r=1000000;//区间右端点
         while(l<r){
           long mid=(l+r+1)/2;
           if(con(number,mid,K)){
              l=mid;
          }
           else{
             r=mid-1;
          }
        }
         System.out.println(l);
         scan.close();
    }
     public static boolean con(int number[][],long num,long k){
       long count=0;
       for(int i=0;i<number.length;i++){
         long ans=(number[i][0]/num)*(number[i][1]/num);
         count+=ans;
      }
       if(count>=k){
         return true;
      }
       return false;
    }
 }

(2.)山


import java.util.Scanner;
 // 1:无需package
 // 2: 类名必须Main, 不可修改
 
 public class Main {
  
    public static boolean check(int a) {
        String str=""+a;
        int i=0; 
        int j=str.length()-1;
        while(i<j) {
            if(str.charAt(i)!=str.charAt(j)||str.charAt(i)>str.charAt(i+1)) {
                break;
            }
            i++;j--;
        }
        if(i<j) {
            return false;
        }
        return true;
    }
   
    public static void main(String[] args) {
        int res=0;
        for(int i=2022;i<=2022222022;i++) {
             
            if(check(i)) {
                res++;
            }
 }
        System.out.println(res);
  
 
    }
 
   
 }

(3.)末尾零

满足 �N ! 的末尾恰好有 �K 个 0 的最小的 �N 是多少?

如果这样的 �N 不存在输出 −1−1 。


import java.util.Scanner;
 // 1:无需package
 // 2: 类名必须Main, 不可修改
 
 public class Main {
     public static void main(String[] args) {
         Scanner scan = new Scanner(System.in);
         //在此输入您的代码...
         long K=scan.nextLong();
         long l=1;
         long r=(long)9e18;
         while(l<r){
           long mid=(l+r)/2;
           if(find(mid)>=K){
             r=mid;
          }
           else{
             l=mid+1;
          }
           
        }
         if(find(l)==K){
        System.out.println(l);
      }
      else{
        System.out.println(-1);
      }
         scan.close();
         
    }
     public static long find(long num){
      long res=0;
      while(num!=0){
        res+=num/5;
        num=num/5;
      }
 return res;
    }
 }
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇