codeforces 521div3(D Cutting Out)java

举报
bigsai 发表于 2021/02/03 02:30:03 2021/02/03
2.2k+ 0 0
【摘要】 题目链接 测试用例: 很多情况会一直wa是因为题意没用读懂,进入自己的圈子无限wa,气的记录下来。。下次不能这么天真。 题意:给数字n和k,n是数字串的长度,k是要将数字分成的份数。让这么多份的数字出现次数最多。 思路: ①首先说说我的错误思路,我想到将数字预处理,先将数字按照出现的次数排序,提取前K个。那么最坏的情况就是这K种都取。出现的次数最大为此时第k个数出...

题目链接
在这里插入图片描述
测试用例:
在这里插入图片描述
很多情况会一直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;
		}
	}

}
  
 

如果对后端、爬虫、数据结构算法等感性趣欢迎关注我的个人公众号交流:bigsai

文章来源: bigsai.blog.csdn.net,作者:Big sai,版权归原作者所有,如需转载,请联系作者。

原文链接:bigsai.blog.csdn.net/article/details/84401349

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

作者其他文章

评论(0

抱歉,系统识别当前为高风险访问,暂不支持该操作

    全部回复

    上滑加载中

    设置昵称

    在此一键设置昵称,即可参与社区互动!

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。