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;
}
| 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;
}
| 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;
}
| cs |
