好看的历史书籍推荐,完美世界txt下载

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案

2022年第十三屆藍橋杯Java省賽B組試題D:最少刷題數(shù)(AC)-創(chuàng)新互聯(lián)

藍橋云課最少刷題數(shù)評測

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

題目以及樣例解釋

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

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

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

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

第一位同學(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題

思路分析

按照我們常用的思路~

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

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

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

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

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

AC代碼(Java實現(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海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

本文名稱：2022年第十三屆藍橋杯Java省賽B組試題D:最少刷題數(shù)(AC)-創(chuàng)新互聯(lián)
分享鏈接：http://fisionsoft.com.cn/article/cejeso.html

新聞中心

其他資訊