藍(lán)橋云課 最少刷題數(shù)評(píng)測(cè)

創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設(shè),澠池企業(yè)網(wǎng)站建設(shè),澠池品牌網(wǎng)站建設(shè),網(wǎng)站定制,澠池網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,澠池網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競爭力。可充分滿足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。試題內(nèi)容 題目以及樣例解釋

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

題目中的解題重點(diǎn)句在于: 比他刷題多的同學(xué)不超過比他刷題少的同學(xué)

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

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

第一位同學(xué):12道題 比他多：15、20 ；比他少：6、10 無需再刷題

第二位同學(xué)：10道題 比他多：12、15、20；比他少：6 需要刷3道題

注意一下這里 如果刷兩道題 那么比他多的是2道比他少的是一道題還是不符合題意，需要再多刷一道題

第三位同學(xué)：15道題 比他多：20； 比他少：6、10、12 無需再刷題

第四位同學(xué)：20道題 比他多：無； 比他少：6、10、12、15 無需再刷題

第五位同學(xué)：6道題 沒有比他更少的 根據(jù)第二位同學(xué) 應(yīng)該刷7題

思路分析

按照我們常用的思路~

要找到幾個(gè)同學(xué)刷題數(shù)量的中間值，每位同學(xué)和中間值去比較判斷，如果刷題數(shù)和人數(shù)符合要求，無需再刷題就可以；如果不符合就要刷題到中間數(shù)+1才可符合題意；中間值的求法與人數(shù)的奇偶性有關(guān)，這還需要分類討論。那么如果幾個(gè)同學(xué)刷題數(shù)量一樣如：3 10 10 12 14 求法又需要去單獨(dú)判斷 是不是特別復(fù)雜?。?！(看過別人的題解~中值判斷的做法都是相當(dāng)復(fù)雜，有些還存在著些許問題，甚至我改完以后好不容易沒有瑕疵還被卡超時(shí)了😭)

下面我們重新來分析一下這道題目，看看有沒有其他的思路和方法

對(duì)于每一個(gè)學(xué)生而言，我們都需要記錄刷題數(shù)目比它多的學(xué)生和刷題數(shù)目比他少的學(xué)生，那么我們是不是就可以開一個(gè)數(shù)組記錄下刷每道題的人數(shù)有多少。那么我們是不是就可以得到比某一道題目多或者少的同學(xué)的數(shù)量呢？ 這里是不是就可以想到前綴和數(shù)組，這樣就可以在O(1)的時(shí)間復(fù)雜度之下得到任意區(qū)間內(nèi)的刷題學(xué)生的數(shù)量，這樣就解決了我們開始需要查詢的問題

接下來，我們繼續(xù)分析：如果我們用cnt[]數(shù)組記錄前綴和來表示學(xué)生刷題的數(shù)量，那么我們假設(shè)現(xiàn)在有一個(gè)學(xué)生的刷題數(shù)量為x,那么刷題數(shù)量比他少的同學(xué)就是cnt[x-1]，刷題數(shù)兩比他多的同學(xué)就是cnt[N]-cnt[x],刷題數(shù)目一樣多的包括自己在內(nèi)就記作cnt[x]。

隨著刷題數(shù)量的增加，比我刷題少的同學(xué)數(shù)量在增多，比我刷題多的同學(xué)數(shù)量在減少，當(dāng)我們達(dá)到了某一個(gè)臨界條件時(shí)，無論你再刷多少題目都是符合題意的。也就是說我們題目中的最少刷題數(shù)就是找到一個(gè)a到正無窮區(qū)間左側(cè)臨界的最小值。由于這個(gè)過程符合二段性的特點(diǎn)，我們自然可以想到二分答案的算法來解決！ 所以這道題目就是利用前綴和+二分的思想來解決題目。（利用快讀快寫加快運(yùn)行速度）

AC代碼(Java實(shí)現(xiàn))

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

public class B組真題最少刷題數(shù) {
    static int N=100010;
    static int[] a=new int[N];
    //cnt[i]表示刷了i道題目的人數(shù)
    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();
    }
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前名稱：2022年第十三屆藍(lán)橋杯Java省賽B組試題D:最少刷題數(shù)(AC)-創(chuàng)新互聯(lián)
本文網(wǎng)址：http://www.rwnh.cn/article30/cejeso.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、網(wǎng)站改版、品牌網(wǎng)站建設(shè)、靜態(tài)網(wǎng)站、ChatGPT、云服務(wù)器

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)