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

【算法提升】分组 day_tow

news 2025/6/2 23:24:37

1.分组

在这里插入图片描述

1.1 解析

个人认为这题最难的点在于如何想到使用二分的算法来解题。正向求解：就是去看每一组中需要分多少个人，但是这样求解代码我根本写不出来。
所以根据正难则反的思想，我们可以从最终结果去倒推。枚举最终的分配结果中，最多的人数(设为x)

在这里插入图片描述

如果你对二分非常熟悉，你就很敏锐的发现这题可以使用二分来求解当然需要确定左右边界
左边界最小就是1，右边界就是所有声部的种类中，人数最多的那个数量当然上图的a,b,c这些人数需要使用hash表来存储。

1.2细节问题

大致的逻辑说完之后，我们就要看一些细节问题，如果声部的种类大于要分的组数，那这是无法分成的，所以需要特判一下。

然后就是二分的细节，注意这里是求最小，所以二分时要注意写法，

多提一嘴如何判断 == 的情况，比如这个当sum == m的时候还可能有更优的解法sum<=m所以这里只处理大于的情况

希望看到这里你能自己动手去写一下代码，代码能力也是非常重要的一部分！

1.3代码

#include<iostream>
#include<unordered_map>
#include<vector>
#include<cmath>using namespace std;
int main()
{//1.输入int n=0,m=0;cin>>n>>m;vector<int> nums(n);for(int i=0;i<n;i++)cin>>nums[i];//2.输出//思路枚举+二分，枚举出最终的分配结果中最多的人数，unordered_map<int,int> hash;//统计出相同声部的人的个数for(auto x:nums)hash[x]++;//特判if(hash.size()>m){cout<<-1<<endl;return 0;}//1.left最小为1，right右边界为hash表中的最大人数int max_right=0;for(auto& [a,b]:hash){max_right=max(max_right,b);}int left=0,right=max_right;while(left<right){int mid=left+(right-left)/2;int sum=0;//统计出当最多人数为mid时的组数for(auto& [a,b]:hash){sum+=(b/mid+(b%mid==0 ? 0 :1));if(sum>m)    break;}//多提一嘴如何判断==的情况，比如这个当sum==m的时候还可能有更优的解法sum<=m所以这里只处理大于的情况if(sum>m)//组分太多，说明最多人数太少了 left=mid+1;elseright=mid;}cout<<left<<endl;return 0;
}