题目描述
给你一个下标从 0 开始的整数数组 tasks ,其中 tasks[i] 表示任务的难度级别。在每一轮中,你可以完成 2 个或者 3 个 相同难度级别 的任务。
返回完成所有任务需要的 最少 轮数,如果无法完成所有任务,返回 -1 。
样例
输入:tasks = [2,2,3,3,2,4,4,4,4,4]
输出:4
解释:要想完成所有任务,一个可能的计划是:
- 第一轮,完成难度级别为 2 的 3 个任务。
- 第二轮,完成难度级别为 3 的 2 个任务。
- 第三轮,完成难度级别为 4 的 3 个任务。
- 第四轮,完成难度级别为 4 的 2 个任务。
可以证明,无法在少于 4 轮的情况下完成所有任务,所以答案为 4 。
算法1
(暴力枚举)
2^m+3^n=k
class Solution {
public:
int minimumRounds(vector<int>& tasks) {
unordered_map<int, int>count;
int ans = 0;
for (int i = 0; i < tasks.size(); ++i)
count[tasks[i]]++;
for (auto it : count)
{
int del = 0x3f3f3f;
for (int i = 0; i < 99999; ++i)
{
if (3*i > it.second)
break;
for (int j = 0; j < 9999; ++j)
{
if (3*i + 2*j > it.second) break;
if (3 * i + 2 * j == it.second)
del = min(del, i + j);
}
}
if (del == 0x3f3f3f)
{
std::cout << it.first << " " << it.second << " " << del << std::endl;
return -1;
}
else ans += del;
//std::cout << it.first << " " << it.second<<" "<<del << std::endl;
}
return ans;
}
};
算法2
贪心
频率是 111,说明这种任务无法完成。
频率是 3×k3\times k3×k,kkk 为 ≥1\ge 1≥1 的整数。每次完成 333 个,kkk 轮完成。
频率是 3×k+23\times k+23×k+2,kkk 为 ≥0\ge 0≥0 的整数。其中 3×k3\times k3×k 个任务需要 kkk 轮完成,剩下 222 个任务需要 111 轮完成。
频率是 3×k+13\times k+13×k+1,kkk 为 ≥1\ge 1≥1 的整数。其中 3×(k−1)3\times (k-1)3×(k−1) 个任务需要 (k−1)(k-1)(k−1) 轮完成,剩下 444 个任务需要 222 轮完成。
C++ 代码
class Solution {
public:
int minimumRounds(vector<int>& tasks) {
unordered_map<int, int> cnt;
for (int t : tasks) {
cnt[t]++;
}
int res = 0;
for (auto [_, v] : cnt) {
if (v == 1) {
return -1;
} else if (v % 3 == 0) {
res += v / 3;
} else {
res += v / 3 + 1;
}
}
return res;
}
};