题目描述：
给你一个长度为 n 下标从 0 开始的整数数组 nums 。
我们想将下标进行分组，使得 [0, n - 1] 内所有下标 i 都 恰好 被分到其中一组。
如果以下条件成立，我们说这个分组方案是合法的：
- 对于每个组
g ，同一组内所有下标在 nums 中对应的数值都相等。 - 对于任意两个组
g1 和 g2 ，两个组中 下标数量 的 差值不超过 1 。
请你返回一个整数，表示得到一个合法分组方案的 最少 组数。
数据范围：
$1\le nums.len \le 10^5, 1\le nums[i] \le 10^9$
题解：
直接考虑贪心。先统计每种数的个数，然后构造一个新数组 $a$ 。
每组中的最大数量只能是频率最低的次数 $minx$ 。
直接从 $[minx, 1]$ 开始check，check成功的话就直接退出。
关键在于如何check，有两种策略。
- 先全凑成 $mid$ ，然后利用余数凑出来 $mid + 1$ 。然后考虑拆掉几组 $mid$ ，将前面的 $mid$ 凑成 $mid + 1$ 。
- 假设凑成 $p$ 组 $mid$ ，余数为 $r$ 。则如果 $r > p$ ，返回 $-1$ 。
- $r \le p$ 时，前面可以先用余数凑出来 $r$ 组 $mid + 1$ ，剩下来 $p - r$ 组 $mid$ 。考虑从 $p - r$ 组 $mid$ 中抽出来 $k$ 组 $mid$ 全拆成 $1$ 加到剩余的 $mid$ 上。肯定需要保证 $p - r - k \ge k \times mid$ ，保证剩下的 $mid$ 组数是大于 $k \times mid$ 的。即 $p - r \ge k \times (mid + 1)$ 。
- 如果满足 $p - r \ge k \times (mid + 1)$ ，则需要分成 $p - k$ 组。不满足则需要分成 $p$ 组。
- 先凑成 $mid + 1$ ，然后考虑余数 $r, 0\le r \le mid$ 。如果余数不等于 $0$ ，将余数利用 $mid + 1$ 拆出来的 $1$ 凑成 $mid$ 。
代码：
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int check(int mid, vector<int> &a)
{
int ret = 0;
for (auto &x : a)
{
int p = x / mid;
int r = x % mid;
if (p < r)
return -1;
if ((p - r) >= (mid + 1))
{
ret += p - (p - r) / (mid + 1);
}
else
{
ret += p;
}
}
return ret;
}
int minGroupsForValidAssignment(vector<int> &nums)
{
unordered_map<int, int> cnt;
int minx = INF;
for (auto &x : nums)
{
cnt[x]++;
}
vector<int> a;
for (auto &[key, value] : cnt)
{
a.emplace_back(value);
minx = min(minx, value);
}
if (a.size() == 1)
return 1;
for (int i = minx; i >= 1; --i)
{
int ret = check(i, a);
if (ret != -1)
{
return ret;
}
}
return 1;
}
};
|
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int check(int mid, vector<int> &a)
{
int ret = 0;
for (auto &x : a)
{
int p = x / mid;
int r = x % mid;
if (p < r)
return -1;
if ((p - r) >= (mid + 1))
{
ret += p - (p - r) / (mid + 1);
}
else
{
ret += p;
}
}
return ret;
}
int check2(int mid, vector<int> &a)
{
int ret = 0;
for (auto &x : a)
{
int p = x / (mid + 1);
int r = x % (mid + 1);
if(r == 0)
ret += p;
else
{
if (p < mid - r)
return -1;
ret += p + 1;
}
}
return ret;
}
int minGroupsForValidAssignment(vector<int> &nums)
{
unordered_map<int, int> cnt;
int minx = INF;
for (auto &x : nums)
{
cnt[x]++;
}
vector<int> a;
for (auto &[key, value] : cnt)
{
a.emplace_back(value);
minx = min(minx, value);
}
if (a.size() == 1)
return 1;
for (int i = minx; i >= 1; --i)
{
int ret = check2(i, a);
if (ret != -1)
{
return ret;
}
}
return 1;
}
};
|