codeforces 521div3(D Cutting Out)java
题目链接
测试用例：
很多情况会一直wa是因为题意没用读懂，进入自己的圈子无限wa，气的记录下来。。下次不能这么天真。
题意：给数字n和k，n是数字串的长度，k是要将数字分成的份数。让这么多份的数字出现次数最多。
思路：
①首先说说我的错误思路，我想到将数字预处理，先将数字按照出现的次数排序，提取前K个。那么最坏的情况就是这K种都取。出现的次数最大为此时第k个数出现的次数（这是最坏的情况）。我刚开始认为出现最小的次数就是排序中value最小的那个。出现最大次数的可能性就是第一出现的次数，后来发现我的想法是错误，举个例子：测试数据1 1 1 1 1 1 2 2 2 2 2 2，k=3的时候，数值的种类还没三总。只是对应1：5次，2：5次。然而结果是1 1 1 2 2，出现两次。看来次数跟最小出现次数没关系呢。要从头开始遍历呢。
②：看数据范围，，如果要求不多勉强可以暴力，数据范围也在二分的范围内。然后看了其他大佬的教程，清一色二分。。我先用了没有二分的方法过。然后加上二分。
没有二分处理思想为：设初始出现的次数q=1为一次开始遍历。总可能出现次数（模拟的K）一旦超过k停止当前循环。记录次数，这就是目前的最大次数。然后次数递增遍历直到count小于K停止次数的递增。然后再遍历list每个元素，除以出现的次数。直到总和为k次 。
二分：二分就是对次数进行二分。最大可能的次数为第一个出现的次数（不可能超过）。所以就left，right再1和max中二分查找。
可能是数据不太强，二分只比第一次快了一点点。但是这题的思想还是二分 排序处理。
附上二分代码（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 自动生成的方法存根
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]);//这个点的次数 list.add(no); }
}
list.sort(com); int max=list.get(0).value;//出现最多的次数//不可能超过的次数
int value=0;//最终出现的次数
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;//次数 break; } } if(count<k) {break;}
}
int time=0;//次数，到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>() {
@Override
public int compare(node o1, node o2) { // TODO 自动生成的方法存根 return o2.value-o1.value;
} };
static class node
{
int index;//数值
int value;// public node() {}
public node(int index,int value)
{ this.index=index; this.value=value;
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
如果对后端、爬虫、数据结构算法等感性趣欢迎关注我的个人公众号交流：bigsai
文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。
原文链接：bigsai.blog.csdn.net/article/details/84401349
- 点赞
- 收藏
- 关注作者
评论（0）