藍橋云課 最少刷題數評測

創新互聯公司是一家集網站建設,澠池企業網站建設,澠池品牌網站建設,網站定制,澠池網站建設報價,網絡營銷,網絡優化,澠池網站推廣為一體的創新建站企業，幫助傳統企業提升企業形象加強企業競爭力。可充分滿足這一群體相比中小企業更為豐富、高端、多元的互聯網需求。同時我們時刻保持專業、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學習、思考、沉淀、凈化自己，讓我們為更多的企業打造出實用型網站。試題內容 題目以及樣例解釋

我們先來分析一下題目，看需要解決什么樣的問題~

題目中的解題重點句在于: 比他刷題多的同學不超過比他刷題少的同學

也就是說對于每一位同學我們要找到刷題比他多的同學和刷題比他少的同學

接下來對樣例進行一下解釋~方面大家更好的理解題目含義

第一位同學: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)-創新互聯
本文網址：http://m.newbst.com/article30/cejeso.html

成都網站建設公司_創新互聯，為您提供品牌網站制作、網站改版、品牌網站建設、靜態網站、ChatGPT、云服務器

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯