题目描述:
在亚马逊Prime Day期间,有大量订单被下单。这些订单已经被打包好,准备在仓库中进行配送。配送员需要以尽可能少的行程将它们送出。
在一次行程中,配送员可以按照以下两个规则选择包裹:
选择两个重量相同的包裹。
选择三个重量相同的包裹。
确定需要的最小行程数以配送这些包裹。如果无法全部配送,则返回-1。
示例
{2, 4, 6, 6, 4, 2, 4} 中,我们需要确定配送员将这些包裹送出所需的最小行程数。
首先,我们可以观察到存在两个重量相同的包裹:2、2和4、4、4。根据规则,我们可以选择两个或三个重量相同的包裹进行配送。
以下是一种可能的方案:
第一次行程:
- 选择两个重量为2的包裹。
第二次行程:
- 选择两个重量为4的包裹。
第三次行程:
- 选择两个重量为6的包裹。
通过这个方案,我们成功将所有包裹送出,并且只需要3次行程。
因此,对于示例 {2, 4, 6, 6, 4, 2, 4},最小行程数为3。
代码
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int minTrips(vector<int> &nums) {
sort(nums.begin(), nums.end());
int l = 0, res = 0;
for (int r = 0; r < nums.size(); r++) {
// find duplictae
while (nums[r] == nums[r + 1] && (r + 1) < nums.size()) r++;
int range = r - l + 1;
if (range % 3 == 0) {
res += range / 3;
}
else if (range % 2 == 0) {
res += range / 2;
} else {
return -1;
}
l = r + 1;
}
return res;
}
int main()
{
vector<int> nums = {2, 4, 6, 6, 4, 2, 4};
int solution = minTrips(nums);
cout << "agent needs minimum " << solution << " to deliver all package" << endl;
return 0;
}