当前位置: 首页 > news >正文

每日OJ题_牛客_分组_枚举+二分_C++_Java

目录

牛客_分组_枚举+二分

题目解析

C++代码

Java代码


牛客_分组_枚举+二分

分组 (nowcoder.com)

描述:

        dd当上了宣传委员,开始组织迎新晚会,已知班里有nnn个同学,每个同学有且仅有一个擅长的声部,把同学们分成恰好mmm组,为了不搞砸节目,每一组里的同学都必须擅长同一个声部,当然,不同组同学擅长同一个声部的情况是可以出现的,毕竟一个声部也可以分成好几个part进行表演,但是他不希望出现任何一组的人过多,否则可能会导致场地分配不协调,也就是说,她希望人数最多的小组的人尽可能少,除此之外,对组内人员分配没有其他要求,她希望你告诉她,这个值是多少,如果无法顺利安排,请输出-1。


题目解析

暴力枚举:从小到大枚举所有可能的最大值,找到第一个符合要求的最大值。

二分优化枚举:二分出符合要求的最大值。

C++代码

#include <iostream>
#include <unordered_map>
using namespace std;
int n, m;
unordered_map<int, int> cnt; // 统计每种声部的⼈数bool check(int x) // 判断最多⼈数为 x 时,能否分成 m 组
{int g = 0; // 能分成多少组for(auto& [a, b] : cnt){g += b / x + (b % x == 0 ? 0 : 1);}return g <= m;
}int main()
{cin >> n >> m;int hmax = 0; // 统计声部最多的⼈数for(int i = 0; i < n; i++){int x;cin >> x;hmax = max(hmax, ++cnt[x]);}int kinds = cnt.size();if(kinds > m) // 处理边界情况{cout << -1 << endl;}else{// // 暴⼒枚举// for(int i = 1; i <= hmax; i++) // 枚举所有的最多⼈数// {// 		if(check(i))// 		{// 			cout << i << endl;// 			break;// 		}// }// ⼆分解法int l = 1, r = hmax;while(l < r){int mid = (l + r) / 2;if(check(mid)){r = mid;}else{l = mid + 1;}}cout << l << endl;}return 0;
}

Java代码

import java.util.*;
public class Main
{public static int n, m;public static Map<Integer, Integer> hash = new HashMap<>(); // 统计每种声部的⼈数public static boolean check(int x) // 判断最多⼈数为 x 时,能否分成 m 组{int g = 0; // 统计能分成多少组for(int a : hash.values()){g += a / x + (a % x == 0 ? 0 : 1);}return g <= m;}public static void main(String[] args){Scanner in = new Scanner(System.in);n = in.nextInt(); m = in.nextInt();int hmax = 0; // 所有声部的最⼤值for(int i = 0; i < n; i++){int x = in.nextInt();hash.put(x, hash.getOrDefault(x, 0) + 1);hmax = Math.max(hmax, hash.get(x));}// 边界情况int kinds = hash.size();if(kinds > m){System.out.println(-1);}else{// // 暴⼒解法// for(int i = 1; i <= hmax; i++)// {// 		if(check(i))// 		{// 			System.out.println(i);// 			break;// 		}// }// ⼆分解法int l = 1, r = hmax;while(l < r){int mid = (l + r) / 2;if(check(mid)){r = mid;}else{l = mid + 1;}}System.out.println(l);}}
}

http://www.mrgr.cn/news/45760.html

相关文章:

  • Linux 学习
  • 登录注册静态网页实现(HTML,CSS)
  • 判断推理(3)
  • Linux系统编程—I/O缓冲区(C语言实现)
  • 极客兔兔Gee-Cache Day5
  • 四.python核心语法
  • alsa-lib 插件 dsnoop 实现简单分析
  • 最大异或对(每周一类)
  • 永磁同步电机环路反步法(backstepping)控制
  • 解决重写QSilder::sliderPress后点击位置与滑块显示位置不一样的问题
  • docker compose入门1—概念介绍
  • open3D release版配置及简单使用
  • 『网络游戏』业务系统基类【08】
  • 网络信息安全法律与政策文件
  • 大厂面试真题-说说AtomicInteger 线程安全原理
  • 如何实现一个基于 HTML+CSS+JS 的任务进度条
  • Windows无需管理员权限,命令轻松修改IP和DNS
  • 【C语言刷力扣】1436.旅行终点站
  • 构建MySQL健康检查Web应用
  • 【陪诊系统】打包问题