3020 개똥벌레 https://www.acmicpc.net/problem/3020
2792 보석상자 https://www.acmicpc.net/problem/2792
3079 입국심사 https://www.acmicpc.net/problem/3079
최근 이분탐색 문제를 많이 풀어서 한꺼번에 올린다.
1. 공항
공항에 $G$개의 게이트가 있다.
비행기 $i$번째 비행기는 [1, $plane_{i}$]게이트 중 하나에 영구적으로 도킹된다.
최대 도킹시킬 수 있는 비행기의 개수를 구하는 문제이다.
set에 도킹되지 않은 게이트들을 저장시켜 greedy하게 $i$번째 비행기를 가장 큰 게이트에 도킹시키면 된다.
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
int N, M;
set<int> v;
int main() {
scanf("%d%d", &M, &N);
for (int m = 1;m <= M;m++)
v.insert(-m);
int ans = 0;
bool f = false;
for (int n = 0;n < N;n++) {
int u;
scanf("%d", &u);
auto get = v.lower_bound(-u);
if (get == v.end()) break;
v.erase(get);
ans++;
}
printf("%d\n", ans);
return 0;
}
| cs |
2. 개똥벌레
석순과 종유석이 번갈아가며 나타나는 동굴이있다.
개똥벌레가 일직선으로 직진하면서 파괴되는 장애물의 개수와 그러한 구간을 구하는 문제이다.
석순은 크기를 찾기위해 lower_bound를 사용하고
종유석은 높이에서 크기를 뺀값을 upper_bound를 이용해서 찾아냈다.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
vector<int> up, down;
int main() {
scanf("%d%d", &N, &M);
for (int n = 1;n <= N;n++) {
int u;
scanf("%d", &u);
if (n & 1) down.push_back(u);
else up.push_back(u);
}
sort(up.begin(), up.end());
sort(down.begin(), down.end());
int ans = 987654321, half_N = N / 2;
int cnt = 0;
for (int m = 1;m <= M;m++) {
int down_iter = lower_bound(down.begin(), down.end(), m) - down.begin();
int up_iter = upper_bound(up.begin(), up.end(), M - m) - up.begin();
int ret = half_N - down_iter + half_N - up_iter;
if (ans > ret) ans = ret, cnt = 1;
else if (ans == ret) cnt++;
}
printf("%d %d\n", ans, cnt);
return 0;
}
| cs |
3. 보석상자
M가지 서로다른 색을 가진 모든 보석을 N명에게 나누어주려한다.
보석을 못받는 사람이있어도 되지만 한사람당 같은색상의 보석만 받을 수 있다.
질투심은 가장 많은 보석을 가진 사람이 가지고있는 보석 개수이다.
모든 보석을 나누어줄때 최소 질투심을 구하는 문제이다.
풀이는 코드로 대체한다.
#include <cstdio>
long long N;
int M, arr[300001];
bool isPossible(int mid) {
long long cnt = 0;
for (int m = 0;m < M;m++) {
if (arr[m] % mid == 0)
cnt += (arr[m] / mid);
else cnt += (arr[m] / mid) + 1;
if (cnt > N) return false;
}
return true;
}
int main() {
scanf("%lld%d", &N, &M);
for (int m = 0;m < M;m++) scanf("%d", &arr[m]);
int l = 1, r = (int)1e9;
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 |
4. 입국심사
N개의 심사대는 각각 심사시간을 가진다.
M명의 심사를 마치는데 걸리는 최소시간을 구하는 문제이다.
충분히 큰 범위를 주고 mid값이 M명을 심사할 수 있는지 판별해서 이분탐색으로 돌리면 구할 수 있다.
#include <cstdio>
#include <algorithm>
using namespace std;
int N, M;
int arr[100001];
bool isPossible(long long mid) {
long long s = 0;
for (int n = 0;n < N;n++)
s += (mid / arr[n]);
if (s < 1LL * M) return false;
return true;
}
int main() {
scanf("%d%d", &N, &M);
for (int n = 0;n < N;n++) scanf("%d", &arr[n]);
sort(arr, arr + N);
long long l = 1, r = (long long)1e18;
while (l <= r) {
long long mid = (l + r) >> 1;
if (isPossible(mid)) r = mid - 1;
else l = mid + 1;
}
printf("%lld\n", l);
return 0;
}
| cs |
같은 대학교 동문이신데 너무 잘하시네요ㅎㅎㅎ 잘 보고있습니다~
답글삭제헉 같은학교라니 반갑습니다!
삭제너무 부족한 실력입니다 ㅠㅠ