-
1498-B, *1300코드포스 2021. 8. 16. 21:54
Problem - 1498B - Codeforces
codeforces.com
문제
- 높이가 1이고 너비가 2의 거듭제곱 형태$(w_{i} = 2^{k})$인 블록 $n(1\leq n \leq 10^{5})$개가 주어진다
- 높이가 1이고 너비가 $w$인 박스가 있을 때, 모든 블록을 담으려면 최소 몇 개의 박스가 필요한가?
(단, $w \geq \mathrm{max(w_{i})}$
풀이1
Greedy
너비가 큰 블록부터 상자에 넣는다.
블록이 들어간 상자들 중 남는 자리가 있으면 그 곳에 채워넣고, 없으면 새로운 상자에 블록을 넣는다Claim 1
$w_{i}$가 2의 거듭제곱 꼴이고 $w_{1}$ 부터 $w_{n}$이 증가할때
$$\begin{aligned}
&w_{1}+w_{2}+\cdot \cdot \cdot+ w_{n}>w_{0},\ w_{1} \leq w_{0}\\
&\Rightarrow \exists \ i\in [1,\ n) \text{ s.t. } w_{1}+w_{2}+\cdot \cdot \cdot+ w_{i}=w_{0}
\end{aligned}
$$$\because$
$w_{1}+w_{2}+\cdot \cdot \cdot+ w_{n}>2,\ w_{1} \leq 2$에 대해
$w_{1}=2$이면 $i = 1$ 에서 준 명제가 성립한다
$w_{1}<2$이면 $w_{1}+w_{2}+\cdot \cdot \cdot+ w_{n}=(1+1)+1+\cdot \cdot \cdot + 1$ 이므로 성립한다$w_{0}=2^{k}(k \geq 1)$일 때 준 명제가 성립한다고 가정하자. 그러면
$w_{1}+w_{2}+\cdot \cdot \cdot+ w_{n}>2^{k+1},\ w_{1} \leq 2^{k+1}$에 대해
i) $w_{1}=2^{k+1}$이면 $i=1$에서 준 명제가 성립하고
ii) $w_{1}<2^{k+1} \text{ i.e. } w_{i}\leq 2^{k}$일 때
$w_{1}+w_{2}+\cdot \cdot \cdot+ w_{j} = 2^{k}$($\because$ 가정)
$w_{i+1}+w_{2}+\cdot \cdot \cdot+ w_{k} = 2^{k},\ k < n$($\because$ 가정)
따라서 $i = k$에서 준 명제가 성립한다수학적 귀납법에 의해 준 명제는 성립한다□
Claim 2
최적 알고리즘을 사용하여 상자에 넣은 블록들의 자리를
사용한 상자의 높이 변화 없이 서로 바꿔서 greedy 알고리즘 결과와 같게 만들 수 있다$pf$
최적 알고리즘의 각 상자를 내림차순으로 정렬하자
또한 편의상 greedy 알고리즘에서 상자에 블록을 넣을 때 항상 왼쪽부터 채워 넣는다고 하자. 그러면
최적 알고리즘과 greedy 알고리즘 모두 각 층마다 왼쪽 블록이 오른쪽 블록보다 크거나 같은 상태이다두 알고리즘의 해를 동시에 아래부터 위쪽으로, 왼쪽부터 오른쪽으로 살펴보자
처음으로 나오는 다른 크기의 블록을 $B_{o},\ B_{g}$ 이라고 하면i) $B_{o} < B_{g}$
$B_{o}$를 포함한 오른쪽에 있는(물론 없을수도 있다) 모든 블록의 너비합은
가. $B_{g}$의 너비보다 크다
- Claim 1 에 의해 앞부분 일부의 너비합은 $B_{g}$와 같다. 이 부분을 위쪽에 있는 $B_{g}$와 바꾼다
나. $B_{g}$의 너비보다 작거나 같다
- 전부 위쪽에 있는 $B_{g}$와 바꾼다ii) $B_{o} > B_{g}$
이런 경우는 존재하지 않는다.
$B_{o}$가 더 크다면 greedy 알고리즘에서 $B_{g}$보다 $B_{o}$를 먼저 배정한다
따라서 $B_{o}$를 배정할 때에는 $B_{g}$ 자리는 비어있거나 $B_{o}$ 보다 큰 블록이 차지하고 있어야한다□priority queue, $O(nlog\ n)$
123456789101112131415161718192021222324252627282930313233343536373839#include <bits/stdc++.h>#define endl "\n"#define loop(i, n) for(int i = 1; i <= n; i++)using namespace std;int n, w;priority_queue<int, vector<int>, less<int> > pq;int main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t;cin >> t;while(t--){cin >> n >> w;int tmp;loop(i, n) {cin >> tmp;pq.push(tmp);}priority_queue<int, vector<int>, less<int> > basket;basket.push(w);while(!pq.empty()){int b = pq.top(); pq.pop();int remain = basket.top(); basket.pop();if(remain >= b) basket.push(remain-b);else{basket.push(remain);basket.push(w-b);}}cout << basket.size() << endl;}return 0;}cs풀이2
Greedy
상자에 가장 큰 블록을 넣는다
남은 공간에 들어갈 수 있는 가장 큰 블록을 찾아 넣는다. 없으면 새로운 상자에 그 블록을 넣는다(반복)Claim 3
최적 알고리즘을 사용하여 상자에 넣은 블록들의 자리를
사용한 상자의 높이 변화 없이 서로 바꿔서 greedy 알고리즘 결과와 같게 만들 수 있다$pf$
최적 알고리즘의 각 상자를 내림차순으로 정렬하자
또한 편의상 greedy 알고리즘에서 상자에 블록을 넣을 때 항상 왼쪽부터 채워 넣는다고 하자. 그러면
최적 알고리즘과 greedy 알고리즘 모두 각 층마다 왼쪽 블록이 오른쪽 블록보다 크거나 같은 상태이다두 알고리즘의 해를 동시에 아래부터 위쪽으로, 왼쪽부터 오른쪽으로 살펴보자
처음으로 나오는 다른 크기의 블록을 $B_{o},\ B_{g}$ 이라고 하면i) $B_{o} < B_{g}$
$B_{o}$를 포함한 오른쪽에 있는(물론 없을수도 있다) 모든 블록의 너비합은
가. $B_{g}$의 너비보다 크다
- Claim 1 에 의해 앞부분 일부의 너비합은 $B_{g}$와 같다. 이 부분을 위쪽에 있는 $B_{g}$와 바꾼다
나. $B_{g}$의 너비보다 작거나 같다
- 전부 위쪽에 있는 $B_{g}$와 바꾼다ii) $B_{o} > B_{g}$
이런 경우는 존재하지 않는다
greedy 알고리즘에서 $B_{g}$를 배열할 시점에 $B_{o}$ 블록도 아직 배정하지 않은 상태이다
greedy 알고리즘은 큰 블록을 우선으로 배정하므로
$B_{o}$가 더 큰 블록이었다면 $B_{o}$을 배정했을 것이다□bitmasks, $O(nlog\ \mathrm{w_{max}})$
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include <bits/stdc++.h>#define endl "\n"#define loop(i, n) for(int i = 1; i <= n; i++)using namespace std;int n, w;int main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t;cin >> t;while(t--){cin >> n >> w;vector<int> cnt(20);int tmp;loop(i, n){cin >> tmp;cnt[log2(tmp)]++;}int res = 1, remain = w;loop(i, n){int largest = -1;for(int size = 19; size >= 0; size--){if(cnt[size] && (1 << size) <= remain) {largest = size;break;}}if(largest == -1){res++;remain = w;for(int size = 19; size >= 0; size--){if(cnt[size] && (1 << size) <= remain) {largest = size;break;}}}cnt[largest]--;remain -= 1 << largest;}cout << res << endl;}return 0;}csmultiset, $O(nlog\ n)$
12345678910111213141516171819202122232425262728293031323334353637383940414243#include <bits/stdc++.h>#define endl "\n"#define loop(i, n) for(int i = 1; i <= n; i++)using namespace std;int n, w;int main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t;cin >> t;while(t--){cin >> n >> w;multiset<int> ms;int tmp;loop(i, n){cin >> tmp;ms.insert(tmp);}int res = 1, remain = w;while(!ms.empty()){auto it = ms.upper_bound(remain);if(it != ms.begin()){it--;remain -= *it;ms.erase(it);}else{res++;remain = w;}}cout << res << endl;}return 0;}cs풀이3
상자의 개수 $cnt$가 주어졌을 때 모든 블록을 넣을 수 있는지 검사할 수 있다면
이진탐색을 통해 $cnt$의 값을 구해낼 수 있다먼저, 동일한 크기의 블록만을 상자에 넣는 경우를 생각하자
블록의 크기가 $4$일때 하나의 상자에는 최대 $\left \lfloor \frac{w}{4} \right \rfloor$개 들어가므로
상자의 개수가 $cnt$개이면 최대 수용할 수 있는 블록의 개수는
$$suff_{4} = cnt\left \lfloor \frac{w}{4} \right \rfloor$$따라서 크기가 $4$인 블록의 개수가 $suff_{4}$보다 크면 $cnt$를 늘려야 한다
한편, 크기가 $4$인 블록을 모두 넣을 수 있을때 크기가 $2$인 블록까지 추가하여 넣을 수 있는지 살펴보자
크기가 $4$인 블록은 크기가 $2$인 블록 두개를 붙여놓은 것으로 생각한다
그러면
$$suff_{2} = cnt\left \lfloor \frac{w}{2} \right \rfloor$$따라서 2$\times$($4$개수)+($2$개수)가 $suff_{2}$보다 작으면 크기가 $4$인 블록과 $2$인 블록 모두를 상자에 담을 수 있다
※ 크기가 $4$인 블록이 들어가는지 반드시 먼저 확인해야 한다.
이는 크기가 $4$인 블록이 짤리지 않았음을 보장해준다
($4$블록은 다 들어가므로 그대로 두고 $2$를 채워 넣는다고 생각)binary search, $O(n+log\ \mathrm{w_{max}}\cdot log\ n)$
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include <bits/stdc++.h>#define endl "\n"#define loop(i, n) for(int i = 1; i <= n; i++)using namespace std;array<int, 20> arr;int n, w;bool valid(int cnt){for(int i = 19; i >= 0; i--){long long suff = 1LL*cnt*(w/(1 << i));if(arr[i] > suff) return false;}return true;}int main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t;cin >> t;while(t--){cin >> n >> w;for(int i = 0; i < 20; i++) arr[i] = 0;int tmp;loop(i, n){cin >> tmp;arr[log2(tmp)]++;}for(int i = 18; i >= 0; i--) arr[i] += 2*arr[i+1];int lo = 1, hi = n;int ans = -1;while(lo <= hi){int mid = (lo + hi) / 2;if(valid(mid)){hi = mid - 1;ans = mid;}else lo = mid + 1;}cout << ans << endl;}return 0;}cs'코드포스' 카테고리의 다른 글
1283-D, *1800 (0) 2021.09.16 1560-A, *800 (0) 2021.08.30 1553-C, *1200 (0) 2021.08.15 1553-D, *1500 (0) 2021.08.15 1554-A, *800 (0) 2021.08.15