题目描述
亚马逊配送中心每天派送包裹。有n个配送中心,每个中心有parcels个包裹需要派送。每天,至少还有一个包裹的配送中心会派送相等数量的包裹。
问题:找出派送所有包裹所需的最少天数。
示例:
假设 parcels = [2, 3, 4, 3, 3],每天至少还有一个包裹的中心会派送相等数量的包裹。
可以按照以下方式派送包裹:
第1天:每个配送中心派送2个包裹,剩余包裹数量为[0, 1, 2, 1, 1]。
第2天:每个配送中心派送1个包裹,剩余包裹数量为[0, 0, 1, 0, 0]。
第3天:每个配送中心派送1个包裹,剩余包裹数量为[0, 0, 0, 0, 0]。
通过最少天数派送所有包裹,需要3天
思路
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minimumDays(vector<int>& parcels) {
int days = 0;
int totalDeliver = 0;
sort(parcels.begin(), parcels.end());
for (int i = 0; i < parcels.size(); i++) {
parcels[i] -= totalDeliver;
if (parcels[i] <= 0) continue;
int deliver = max(parcels[i], 1);
parcels[i] -= deliver;
totalDeliver += deliver;
days++;
}
return days;
}
int main() {
vector<int> parcels = {2, 3, 4, 3, 3};
int minDays = minimumDays(parcels);
cout << "Minimum number of days needed: " << minDays << endl;
return 0;
}