模板演示网站,一线品牌全屋定制排名,徐州旅游的网站建设,windows vps offline性x1. 题意
给定一组数。将这些数进行分组#xff0c;使得
组内所有元素相等任意两个组的大小相差不超过1
合法分组的最少组数
2. 题解
直接引用别人的题解算了吧#xff0c;是一个数学变换的题。
核心是当 ⌊ v k ⌋ ≥ v % k \lfloor \frac {v}{k} \rfloor \ge v \%k ⌊…1. 题意
给定一组数。将这些数进行分组使得
组内所有元素相等任意两个组的大小相差不超过1
合法分组的最少组数
2. 题解
直接引用别人的题解算了吧是一个数学变换的题。
核心是当 ⌊ v k ⌋ ≥ v % k \lfloor \frac {v}{k} \rfloor \ge v \%k ⌊kv⌋≥v%k时 v v v一定可以分为 k k k和 k 1 k1 k1的组。
且此时分得的组数最少为 ⌈ v k 1 ⌉ \lceil \frac{v}{k1} \rceil ⌈k1v⌉ 首先统计 n u m s nums nums得到数组 a r r arr arr。题目要求找到一个分组基准 d d d使得 a r r arr arr的每个元素可以由若干个 d d d和 d 1 d1 d1组成。对于元素 a a a假设 a x d y ( d 1 ) a x d y ( d 1 ) a x d y ( d 1 ) axdy(d1)axdy(d1)axdy(d1) axdy(d1)axdy(d1)axdy(d1)满足分组条件变形得 a ( x y ) d y a ( x y ) d y a ( x y ) d y a(xy)dya(xy)dya(xy)dy a(xy)dya(xy)dya(xy)dy。另设 a p d r apdr apdr其中 p a / / d , r a % d pa//d,ra\%d pa//d,ra%d。则 a a a可以写成 a ( p − k ) d ( k d r ) a(p−k)d(kdr) a(p−k)d(kdr)。式子联立得 p − k x y ≥ y k d r p−kxy≥ykdr p−kxy≥ykdr因此满足分组条件的充要条件是 p − k ≥ k d r p−k≥kdr p−k≥kdr。注意到当 k 0 k0 k0时 p − k p−k p−k最大 k d r kdr kdr最小。因此只需要 p ≥ r p≥r p≥r即可满足分组条件。 要求的最优解是 x y p − k xyp−k xyp−k的最小值。由 p − k ≥ k d r p−k≥kdr p−k≥kdr得 k ≤ ( p − r ) / / ( d 1 ) k≤(p−r)//(d1) k≤(p−r)//(d1)因此最优解为 p − ( ( p − r ) / / ( d 1 ) ) p− ((p−r)//(d1)) p−((p−r)//(d1)) 代码
class Solution {
public:int minGroupsForValidAssignment(vectorint nums) {// 3 2 3 2 3// 333 22 // 10 10 10 3 1 1// 11 1010 10 3unordered_mapint,int um;for (auto v : nums)um[v];vectorint g;for (auto [k, v]: um)g.push_back(v);sort(g.begin(), g.end() );int ans 0;for (int d g[0]; d 0; --d) {ans 0;for ( auto v: g) {int r v % d ;if ( v / d r) {ans 0; break;}ans (v d)/(d 1); }if (ans)break;}return ans;}
};3. 引用
03xf 云飘飘 Jacky
