15708 미네크래프트

15708 미네크래프트 https://www.acmicpc.net/problem/15708
Codeforces #470 (Div.2) C - Producing Snow http://codeforces.com/contest/948/problem/C
14452 Cow Dance Show https://www.acmicpc.net/problem/14452
1781 컵라면 https://www.acmicpc.net/problem/1781   (https://lyzqm.blogspot.com/2017/10/1781.html)

pq와 greedy를 이용한 문제들을 소개하고자 한다.

1. 미네크래프트
시간 T와 N개의 바위를 각각 캐는데 걸리는 시간이 주어지고 옆의 바위로 건너가는 시간P가 주어진다.
캘 수 있는 바위의 최대개수를 구하는 문제이다.

현재 보고있는 바위를 캘지 정하는 것으로 풀지 말고 
지금 까지 봤던 바위들 중 작은 바위들을 캐서 현재 보고있는 바위까지 건너올 수 있게끔 풀어야 한다.

이러한 유형의 문제들은 우선적으로 pq에 넣어서 처리해주는 편이 좋다.

#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; int n, t, p; int arr[MAXN]; priority_queue<int> pq; int main() {     scanf("%d%d%d", &n, &t, &p);     for (int i = 0; i < n; i++) scanf("%d", &arr[i]);     int sum = 0, sze = 0, ans = 0;     for (int i = 0; i < n; i++) {         if (t <= p * i) break;         sze++;         sum += arr[i];         pq.push(arr[i]);         while (!pq.empty() && sum > t) {             sum -= pq.top();             sze--;             pq.pop();         }         if (sum > t) break;         ans = max(ans, sze);         sum += p;     }     printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs

2. Producing Snow 
N일 동안 눈이 $s_{i}$만큼 쌓인다.
각각의 날에 기온은 $t_{i}$이다.
눈이 녹는 정도는 그날 기온에 영향을 받으며 이전에 남았던 눈 또한 녹는다.
각각의 날에 녹는 눈의 양을 구하는 문제이다.


대회때는 못풀었던 아쉬운 문제이다.
pq에 $s_{i}$와 이전에 기온들의 합을 넣어 관리할 수 있다.
눈이 완전히 녹는것은 이전 기온들의 합과 현재 기온의 합보다 작거나 같아지는 경우이다.
아직 pq에 남아있는 크기만큼 눈들 또한 더 녹기 때문에 이것도 더해줘야한다.

#include <bits/stdc++.h> using namespace std; typedef long long ll; int n; const int MAXN = 1e5 + 5; int arr[MAXN]; priority_queue<ll> pq; int main() {     scanf("%d", &n);     for (int i = 0; i < n; i++) scanf("%d", &arr[i]);     ll s = 0;     for (int i = 0, minus; i < n; i++) {         ll ret = 0;         scanf("%d", &minus);         pq.push(-(arr[i] + s));         s += minus;         while (!pq.empty() && -pq.top() <= s) {             ret += -pq.top() - s + minus;             pq.pop();         }         ret += pq.size() * minus;         printf("%lld ", ret);     }     return 0; } Colored by Color Scripter

cs

3. Cow Dance Snow

소들이 춤추는 시간들이 정해져있고 춤을 다 춘 소는 순차적으로 들어간다.

모든 소가 춤을 추는데 걸리는 시간 T를 넘지 않도록 소들이 춤출 수 있는 

최소 사이즈 K를 구하는 문제다. 

이분탐색과 위의 문제처럼 pq를 이용한 기법으로 해결할 수 있다.

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1e6 + 6; int n, t; ll arr[MAXN]; bool ispossible(int idx) {     ll prv = 0, sum = 0;     priority_queue<ll> pq;     for (int i = 0; i < idx; i++) pq.push(-arr[i]);     while (!pq.empty()) {         ll curr = -pq.top();         pq.pop();         sum += (curr - prv);         if (sum > t) return false;         prv = curr;         if (idx < n) pq.push(-sum - arr[idx++]);     }     return sum <= t; } int main() {     scanf("%d%d", &n, &t);     for (int i = 0; i < n; i++) scanf("%lld", &arr[i]);          int l = 1, r = n;     while (l <= r) {         int mid = (l + r) >> 1;         if (ispossible(mid)) r = mid - 1;         else l = mid + 1;     }     printf("%d\n", l);     return 0; } Colored by Color Scripter

cs