題目鏈接

測(cè)試用例：

很多情況會(huì)一直wa是因?yàn)轭}意沒(méi)用讀懂，進(jìn)入自己的圈子無(wú)限wa，氣的記錄下來(lái)。。下次不能這么天真。
題意：給數(shù)字n和k，n是數(shù)字串的長(zhǎng)度，k是要將數(shù)字分成的份數(shù)。讓這么多份的數(shù)字出現(xiàn)次數(shù)最多。

思路：
①首先說(shuō)說(shuō)我的錯(cuò)誤思路，我想到將數(shù)字預(yù)處理，先將數(shù)字按照出現(xiàn)的次數(shù)排序，提取前K個(gè)。那么最壞的情況就是這K種都取。出現(xiàn)的次數(shù)最大為此時(shí)第k個(gè)數(shù)出現(xiàn)的次數(shù)（這是最壞的情況）。我剛開(kāi)始認(rèn)為出現(xiàn)最小的次數(shù)就是排序中value最小的那個(gè)。出現(xiàn)最大次數(shù)的可能性就是第一出現(xiàn)的次數(shù)，后來(lái)發(fā)現(xiàn)我的想法是錯(cuò)誤，舉個(gè)例子：測(cè)試數(shù)據(jù)1 1 1 1 1 1 2 2 2 2 2 2，k=3的時(shí)候，數(shù)值的種類(lèi)還沒(méi)三總。只是對(duì)應(yīng)1：5次，2：5次。然而結(jié)果是1 1 1 2 2，出現(xiàn)兩次。看來(lái)次數(shù)跟最小出現(xiàn)次數(shù)沒(méi)關(guān)系呢。要從頭開(kāi)始遍歷呢。
②：看數(shù)據(jù)范圍，，如果要求不多勉強(qiáng)可以暴力，數(shù)據(jù)范圍也在二分的范圍內(nèi)。然后看了其他大佬的教程，清一色二分。。我先用了沒(méi)有二分的方法過(guò)。然后加上二分。

沒(méi)有二分處理思想為：設(shè)初始出現(xiàn)的次數(shù)q=1為一次開(kāi)始遍歷。總可能出現(xiàn)次數(shù)（模擬的K）一旦超過(guò)k停止當(dāng)前循環(huán)。記錄次數(shù)，這就是目前的最大次數(shù)。然后次數(shù)遞增遍歷直到count小于K停止次數(shù)的遞增。然后再遍歷list每個(gè)元素，除以出現(xiàn)的次數(shù)。直到總和為k次 。
二分：二分就是對(duì)次數(shù)進(jìn)行二分。最大可能的次數(shù)為第一個(gè)出現(xiàn)的次數(shù)（不可能超過(guò)）。所以就left，right再1和max中二分查找。
可能是數(shù)據(jù)不太強(qiáng)，二分只比第一次快了一點(diǎn)點(diǎn)。但是這題的思想還是二分 排序處理。
附上二分代碼（202ms）：

package codeforces521;import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; import java.util.ArrayList; import java.util.Comparator;import java.util.List; public class testD {public static void main(String[] args) throws IOException {// TODO 自動(dòng)生成的方法存根StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();int n=(int)in.nval;in.nextToken();int k=(int)in.nval;int a[]=new int[n];int map2[]=new int[200005];for(int i=0;i<n;i++){in.nextToken();a[i]=(int)in.nval;map2[a[i]]++;}List<node>list=new ArrayList<>();for(int i=0;i<200005;i++){if(map2[i]>0){node no=new node(i, map2[i]);//這個(gè)點(diǎn)的次數(shù)list.add(no);}}list.sort(com);int max=list.get(0).value;//出現(xiàn)最多的次數(shù)//不可能超過(guò)的次數(shù)int value=0;//最終出現(xiàn)的次數(shù)int mid=0;//二分查找/** 二分*/// int l=1;int r=max+1; // while(l<r) // { // mid=(l+r)/2; // // int count=0; // for(int i=0;i<list.size();i++) // { // count+=list.get(i).value/mid; // if(count>=k) // { // value=mid; // l=mid+1; // break; // } // } // if(count<k) // { // r=mid; // } // } // mid=value;for(int q=1;q<=max;q++){//System.out.println(q);int count=0;for(int i=0;i<list.size();i++){count+=list.get(i).value/q;if(count>=k){value=i;mid=q;//次數(shù)break;} }if(count<k){break;}}int time=0;//次數(shù)，到K次就停止for(int i=0;i<list.size();i++){node team=list.get(i);int va=team.value;while(va-mid>=0){va-=mid;time++;if(time>k) {break;}out.print(team.index+" ");}if(time>k)break;}out.flush(); }static Comparator<node>com=new Comparator<node>() {@Overridepublic int compare(node o1, node o2) {// TODO 自動(dòng)生成的方法存根return o2.value-o1.value;} };static class node{int index;//數(shù)值int value;//public node() {}public node(int index,int value){this.index=index;this.value=value;}}}

如果對(duì)后端、爬蟲(chóng)、數(shù)據(jù)結(jié)構(gòu)算法等感性趣歡迎關(guān)注我的個(gè)人公眾號(hào)交流：bigsai

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的codeforces 521div3(D Cutting Out)java的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。