-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
1011.cpp
92 lines (85 loc) · 2.65 KB
/
1011.cpp
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
85
86
87
88
89
90
91
92
__________________________________________________________________________________________________
sample 28 ms submission
class Solution {
bool poss(vector<int>& w, int D,int x)
{
int n=w.size();
int sum=0;int ans=1;
for(int i=0;i<n;i++)
{
if(w[i]>x)return false;
if(sum+w[i]>x)
{
ans++;sum=w[i];
}
else sum+=w[i];
}
if(ans<=D)return true;
return false;
}
public:
int shipWithinDays(vector<int>& weights, int D) {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int start=1;int end=500*25;
while(start<end)
{
int mid=(start+end)>>1;
if(poss(weights,D,mid))end=mid;
else start=mid+1;
}
return start;
}
};
__________________________________________________________________________________________________
sample 32 ms submission
/*
Intuition
The largest capacity (r) we may even need is the sum of weights of all packages.
The smallest capacity (l) is the weight of the largest package.
Optimization: the smallest capacity cannot be less than r / D, which reduces the search interval if we have a lot of small packages (and D is small).
Our result is within this interval.
Linearithmic Solution
We use binary search to find the minimum capacity. For each capacity we analyze, we count the number of days required to ship all packages.
We decrease the capacity if it takes less days than D, and increase otherwise. Note that, when the number of days equals D, this algorithm keeps decreasing the capacity while it can, therefore finding the smallest capacity required.
Time - nLOGn
*/
auto speedup = []() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
return nullptr;
}();
class Solution {
public:
int shipWithinDays(vector<int>& weights, int D) {
int st = 0, ed = 0;
for (const auto& w : weights) {
ed += w;
st = max(st, w);
}
st = max (st, ed / D);
while (st < ed) {
int mid = (st + ed) / 2;
int cnt = 0;
int sum = 0;
int i = 0;
for (; i < weights.size() && cnt < D; ++i) {
sum += weights[i];
if (sum > mid) {
sum = 0;
++cnt;
--i;
}
}
if (i == weights.size()) {
ed = mid;
} else {
st = mid + 1;
}
}
return ed;
}
};
__________________________________________________________________________________________________