二分,二分答案

解法思路

思路一

如果将题目带入现实,就不难理解,就像是分班一样,将若干个人分组,每组里的人要保证来自同一个班,并且每组的人数要尽可能"均匀",然后再加上一些后缀条件就是题意了,如果觉得这个解释不清晰,那就按照你自己的来,只要是能理解的方法都是好方法.

策略:将拥有相同声部的人先全部分到一组里,然后分割他们,每次分割成他的一半,这样能最大程度的减小他们的人数,使用大根堆存储,这样每次分割的组就是人数最大的,正好能削弱最大组的人数,之后一直循环到heap的元素有m个即可,如果一开始heap里的元素就大于m那就证明不能分成m组,没有这样的策略,返回-1即可
听起来是不是很简单,不过听听就行了,千万不要写代码,写了也过不了,我就是,这种策略听起来好像很有道理,但是他是不对的,至于为啥不对,我琢磨了很久也没想出来,主要是牛客他不给不过的测试用例啊,我想破了脑袋,最后还是选择的放弃,各位大佬,如果知道这个解法为啥错,希望能不吝赐教,感谢了.

这种解法只能过20%的测试用例,代码粘在下面了,仅供研究使用.

思路二

枚举最大人数,根据这个最大人数来判断能分多少组,如果能分的组数小于等于m组说明这个最大人数还能再小,于是right指针就能向右移动,反之,如果此时分的组数大于m,这就证明最大人数必须增大了,如果觉得比较抽象,
举个例子:比如你现在有3组数据,此时的最大人数是5,如果你此时将最大人数减一变成4,那你还能分成3组吗?不一定吧,可能就要分成4组,5组……了,这就是二段性.
最大人数和组数具有二段性,就像是当最大人数小的时候,这个组数就能分的越多,当最大人数增大的时候,组数就会变得越小

具体解法:枚举最大人数,这个人数,然后根据最大人数,判断是否能分成m组,直到找到那个最小的最大人数

代码

思路一代码

import java.util.*;
public class Main{
    static class Pair{
        int a,cnt;
        public Pair(int a,int cnt){
            this.a = a;
            this.cnt = cnt;
        }
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        PriorityQueue<Pair> heap = new PriorityQueue<Pair>((x,y) -> y.cnt - x.cnt);
        int[] count = new int[100005];
        for(int i =0;i<n;i++){
            count[in.nextInt()]++;
        }
        
        for(int i=0;i<100005;i++){
            if(count[i] !=0){
                heap.add(new Pair(i,count[i]));
            }
        }
        
        if(heap.size()>m){
            System.out.println(-1);
        }else if(heap.size() == m){
            System.out.println(heap.peek().cnt);
        }else{
            while(heap.size()<m){
                Pair tmp = heap.poll();
                heap.add(new Pair(tmp.a,tmp.cnt/2));
                heap.add(new Pair(tmp.a,tmp.cnt - tmp.cnt/2));
            }
            System.out.println(heap.peek().cnt);
        }
    }
}

思路二代码

这个优化版本的二分其实这里的check判断很多人都会疑惑到底是该让
left = mid +1……还是其他的啥,其实这个要根据题意的二段性,以及二分查找的死循环经验来判断,这个得靠练,多做,多总结,多复习就能学会.

import java.util.*;
public class Main{
    static int m,n;
    static int[] hash = new int[(int)1e5+10];
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        int max =0;
        for(int i =0;i<n;i++){
            int tmp =in.nextInt();
            hash[tmp]++;
            max = Math.max(max,hash[tmp]);
        }
        //其实直接暴力枚举最大人数也能过
//         for(int i = 1;i<=max;i++){
//             if(check(i)){
//                 System.out.println(i);
//                 return;
//             }
//         }
//         System.out.println(-1);
        
        //这一种写法是优化版本的,二分答案,二分最大人数
        int cnt =0;
        for(int i =0;i<n;i++){
            if(hash[i] !=0)cnt++;
        }
        if(cnt >m){
            System.out.println(-1);
            return ;
        }
        int l = 1,r = max;
        while(l<r){
            int mid = l+(r-l)/2;
            if(check(mid)){
                r = mid;
            }else l = mid+1;
        }
         System.out.println(l);
    }
    //判断人数为x时,是否能满足条件:
    public static boolean check(int x){
        int ret =0;
        for(int i=0;i<n;i++){
            ret+=hash[i]/x;
            if(hash[i] % x !=0){
                ret++;
            }
        }
        return ret <= m;
    }

}

二分查找算法

通过上述题目,相信你已经热过身了,对二分已经有了一定的了解,此时我们来详谈二分算法:

以上是我自己总结的一套体系,上面有一些你没有见过的名词,这些名词都是自传,都会详谈,所以不要担心.

前提

注意使用二分之前一定要先排个序

mid的偏向

什么是mid的偏向:
比如你是不是经常写出这样的代码

	int l = 0,r = n-1;
       while(l<r){
           int mid = (l+r)/2;
           if(a[mid] < target){
               l = mid+1;
           }else r = mid;
       }

综上所述:也就是说mid向哪个指针偏移,就是啥偏.

一个小tips,l+(r-l)/2和r+(l-r)/2的区别

上面的简图只需要记住我标记的那俩就行,其他的生僻的可以拿去ZB,
他们的由来:

• 对于左偏第一个(l+r)/2,这是我们再熟悉不过的两个数求平均值了吧,但是当数字比较大时容易出现溢出,所以更推荐左偏第二个.但是为什么第一个是左偏呢?有没有想过这个问题?其实这与计算机内部的计算逻辑和数据的类型有关,我们平时在做计算题的时候
  比如:6/2是不是直接就是等于3,此时计算机计算的也是等于3
  但是对于5/2呢?我们算出来的是2.5,但是计算机呢?如果是整形int,就是将小数部分给完全舍去了就是2,如果是浮点数呢,那就是2.5.由于二分查找都是建立在整形下标的基础上,所以我们势必要考虑到这个偏向的问题,因此对于(l+r)是奇数的情况下,他会舍去小数部分,所以就会发生左偏.是偶数的情况,那就是不偏啊,那就正常找了,这种太平常的情况我们不讨论
• 左偏 l+(r-l)/2

右偏r+(l-r)/2也是同样的思路,同理

• 右偏(l+r+1)/2和左偏(l+r)/2原理一样,就是利用了当被除数是奇数的时候,它除2后的结果要舍弃小数位,所以结果就是商偏小,但是如果将l+r+1就是变相的将原来的被除数从奇数转成偶数,此时精准打击,如果被除数原来是偶数,虽然会变成奇数,但是奇数除以2后可是会偏小的偶,相当于正好校准了一下,这个很好体会,动手画画图就行了
• 右偏l+(r-l+1)/2原理很简单,如上简图

如何避免死循环

为什么要搞懂左偏右偏呢?就是为了让我们写出的二分查找不再死循环,
以下给出一种思考方式,来避免死循环:

对于上述问题,我举的例子中左偏比较多,其实右偏也是一样的逻辑,如果有兴趣,可以分析分析,这里我就不赘述了.

什么时候会死循环

死循环:总结:

• 左偏的时候,含有left = mid
• 右偏的时候,含有right = mid
• 以上两种情况都会导致死循环
  所以我们今后在写二分的时候可以根据,使用左偏是否含有left = mid和右偏是否含有right = mid作为判断死循环的依据

对于一些二分答案的题目

		while(l<r){
            int mid = l+(r-l)/2;
            if(check(mid)){
                r = mid;
            }else l = mid+1;
        }

它的代码可能就是一些check函数含在里面,此时你就不能直接通过什么target来判断了,但是他们的思想是一致的,就比如,上面的那道二分答案题目,当check(最大人数)返回的是true的时候,说明什么?符合啊,就是说当最大人数是mid的时候能保证分成m个组,也就是说我们可以试试还能不能压榨一下最大人数,让最大人数减小一点,看看是否还能满足组成m个组,通过代码能看见这是一个左偏,转换一下就是,左偏,target在左边 => r = mid
所以遇到这种二分答案的题目,是需要具体题目,具体分析,不可死记硬背.

当查找的对象有多个时,查找的是哪个对象

对于左偏

对于右偏

依照左偏的思路直接就能推出来,这里就不赘述了.

当查找的对象不在,没有目标值时

左偏

右偏

和左偏分析,同理.