https://www.acmicpc.net/problem/2805
1. 의사코드
1. 적어도 n이상.. 문제 -> 결정문제로 바꿔서 푼다
2. 정답후보 : 0~20억에 대해 st, en으로 이분탐색
3. 이분탐색 공식은 암기토록 하자.
2. 전체코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m, a[1000000 + 4];
//길이가 x일때, 가질나무가m개 이상인지
int go(ll x) {
ll cur = 0; //x개로 랜선자른 갯수
for (int i = 0; i < n; ++i) {
int tmp = a[i] - x;
if (tmp < 0) continue;
cur += tmp;
}
return cur>=m;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n>>m;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
//sort(a, a + 1000000 + 4);
ll st = 0, en = 2000000000;
while (st < en) {
ll mid = (st + en + 1) / 2;
if (go(mid)) st = mid; //랜선을자를수있으면 -> 더큰길이로잘라도되는지 우측탐색
else en = mid - 1; //랜선을 못자르면 -> 랜선길이를줄여야함 -> 좌측탐색
}
cout << st;
return 0;
}
'Algorithm > 이분탐색' 카테고리의 다른 글
백준 2467 두용액 c++ //이분탐색 정답후보를 탐색하라 (0) | 2024.03.24 |
---|---|
백준 18869 멀티버스2 c++ // 값을 idx로 바꿔라, 이분탐색이용, unique사용법 (0) | 2024.03.11 |
프로그래머스 순위검색 c++ // 이분탐색, db설정 (0) | 2024.01.11 |
백준 1654 랜선자르기 c++ // 이분탐색, parametric search (0) | 2024.01.04 |
백준 2295 세수의합 c++ // 이분탐색 발상 (0) | 2024.01.03 |