2022年第十三届蓝桥杯Java省赛B组试题D:最少刷题数(AC)-创新互联

蓝桥云课 最少刷题数评测

创新互联公司是一家集网站建设,渑池企业网站建设,渑池品牌网站建设,网站定制,渑池网站建设报价,网络营销,网络优化,渑池网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。试题内容 题目以及样例解释

我们先来分析一下题目，看需要解决什么样的问题~

题目中的解题重点句在于: 比他刷题多的同学不超过比他刷题少的同学

也就是说对于每一位同学我们要找到刷题比他多的同学和刷题比他少的同学

接下来对样例进行一下解释~方面大家更好的理解题目含义

第一位同学:12道题 比他多：15、20 ；比他少：6、10 无需再刷题

第二位同学：10道题 比他多：12、15、20；比他少：6 需要刷3道题

注意一下这里 如果刷两道题 那么比他多的是2道比他少的是一道题还是不符合题意，需要再多刷一道题

第三位同学：15道题 比他多：20； 比他少：6、10、12 无需再刷题

第四位同学：20道题 比他多：无； 比他少：6、10、12、15 无需再刷题

第五位同学：6道题 没有比他更少的 根据第二位同学 应该刷7题

思路分析

按照我们常用的思路~

要找到几个同学刷题数量的中间值，每位同学和中间值去比较判断，如果刷题数和人数符合要求，无需再刷题就可以；如果不符合就要刷题到中间数+1才可符合题意；中间值的求法与人数的奇偶性有关，这还需要分类讨论。那么如果几个同学刷题数量一样如：3 10 10 12 14 求法又需要去单独判断 是不是特别复杂！！！(看过别人的题解~中值判断的做法都是相当复杂，有些还存在着些许问题，甚至我改完以后好不容易没有瑕疵还被卡超时了😭)

下面我们重新来分析一下这道题目，看看有没有其他的思路和方法

对于每一个学生而言，我们都需要记录刷题数目比它多的学生和刷题数目比他少的学生，那么我们是不是就可以开一个数组记录下刷每道题的人数有多少。那么我们是不是就可以得到比某一道题目多或者少的同学的数量呢？ 这里是不是就可以想到前缀和数组，这样就可以在O(1)的时间复杂度之下得到任意区间内的刷题学生的数量，这样就解决了我们开始需要查询的问题

接下来，我们继续分析：如果我们用cnt[]数组记录前缀和来表示学生刷题的数量，那么我们假设现在有一个学生的刷题数量为x,那么刷题数量比他少的同学就是cnt[x-1]，刷题数两比他多的同学就是cnt[N]-cnt[x],刷题数目一样多的包括自己在内就记作cnt[x]。

随着刷题数量的增加，比我刷题少的同学数量在增多，比我刷题多的同学数量在减少，当我们达到了某一个临界条件时，无论你再刷多少题目都是符合题意的。也就是说我们题目中的最少刷题数就是找到一个a到正无穷区间左侧临界的最小值。由于这个过程符合二段性的特点，我们自然可以想到二分答案的算法来解决！ 所以这道题目就是利用前缀和+二分的思想来解决题目。（利用快读快写加快运行速度）

AC代码(Java实现)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class B组真题最少刷题数 {
    static int N=100010;
    static int[] a=new int[N];
    //cnt[i]表示刷了i道题目的人数
    static int[] cnt=new int[N];
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out=new PrintWriter(new PrintWriter(System.out));
    public static void main(String[] args) throws IOException {
        int n=Integer.parseInt(br.readLine());
        String[] s=br.readLine().split(" ");
        for (int i = 0; i>1;
                if (cnt[100000]-cnt[mid]<=cnt[mid-1]-1){
                    r=mid;
                }else {
                    l=mid+1;
                }
            }
            out.print(r-a[i]+" ");
        }
        out.flush();
    }
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

当前名称：2022年第十三届蓝桥杯Java省赛B组试题D:最少刷题数(AC)-创新互联
文章URL：http://cdkjz.cn/article/cejeso.html