성현이네 부대의 24-1분기 사격 훈련이 시작되었다!
성현이네 부대의 사격 훈련장에는
$N$개의 표적이 있으며, 그중
$i$번째 표적의 점수는
$s_i$이다. 점수가
$s_i$인 표적을 맞히기 위해선 사격 실력이 최소
$s_i$ 이상이어야 한다. 만약 해당 표적을 성공적으로 맞혔다면, 표적의 점수만큼 사격 점수를 획득하며 사격 실력도 동일한 만큼 증가한다.
이번 사격 훈련에서는 최대
$M$번 사격할 수 있으며, 성현이가 진급에 성공하기 위해서는 획득한 사격 점수의 총합이
$A$점 이상이어야 한다.
사격 훈련을 시작하기 전 초기 사격 점수는
$0$점이다. 성현이는 항상 자신이 맞힐 수 있는 표적 중 얻을 수 있는 사격 점수가 가장 높은 표적을 맞히며, 동일한 표적을 여러 번 맞히는 것도 가능하다.
진급이 절실했던 성현이는 사격 훈련이 시작하기 전 초기 사격 실력이 어느 정도여야 진급에 성공할 수 있을지 궁금해하고 있다. 성현이를 위해, 진급에 성공하기 위한 초기 사격 실력의 최솟값을 구해주자. 항상 진급에 성공할 수 있는 경우만 입력으로 주어진다.
우리는 문제를 보는 순간 아! 라고 외치지 않을까 한다.
느므느므 큰 범위를 보고, 값을 찾는 문제여서 바로 이분탐색으로 접근하였다.
(나중에 더욱 자세히 쓸 예정…)
정답 코드 CPP</>
#define MAX 2'100'000'000#include <iostream>#include <vector>#include <cstring>#include <algorithm>#include <queue>#include <stack>#include <math.h>#include <random>using namespace std;using ull = unsigned long long;using ll = long long;int score[100001];ull n, m, a;bool visited[100001];bool debug_ = false;ull current_ = 0;ull binary_search_(ull current, int depth){ if(depth >= m|| current >= a) return current; int left = 0, right = n-1; current += current_; int val = -1; while(left < right ){ int pivot = (left+ right) / 2; if(score[pivot] < current){ if(pivot+1 < n && score[pivot+1] > current){ val = score[pivot]; break; } left = pivot+1; if(left < 0 || score[left] > current) continue; val = max(val, score[left]); } else if(score[pivot] > current){ right = pivot - 1; if(right < 0|| score[right] > current) continue; val = max(val, score[right]); } else {val = score[pivot]; break;} } if(val == -1) val = score[left]; if(val > current) return 0; current-=current_; ull result = binary_search_(current + val, depth+1); return result;}int main(){ cin >> n >> m >> a; int limit = 0; for(int i = 0; i < n; i++){ cin >> score[i]; limit = max(limit, score[i]);} sort(score, score+n); if(n == 1){ cout << score[0]; return 0; } int left = 1, right = limit; ull result = MAX; while(left <= right){ current_ = (left + right) / 2; ull tmp = binary_search_(0, 0); if(tmp >= a){ result = min(current_, result); right = current_-1; }else{ left = current_+1; } } cout << result; return 0;}
compy.log