[C++] 백준 19592: 장난감 경주

문제

https://www.acmicpc.net/problem/19592

19592번: 장난감 경주

 

해결방법

1. 자신을 뺀 참가자의 완주하는 데 걸리는 시간을 vector에 넣고 자신의 속도만 따로 speed 변수에 저장한다.

2. vector를 오름차순으로 정렬한다. 이 때 vector[0]은 현재 1등이다.

3. 부스터 없이 완주하는데 걸리는 시간이 vector[0]보다 작으면 단독 우승이므로 0을 출력한다.

4. 부스터를 다 사용했을 때 남은 거리를 자신의 속도로 나눈 값 (x-y)/speed에 부스터 사용에 걸린 1초를 더해준 값이 vector[0]보다 크거나 같으면 단독 우승이 불가능하므로 -1을 출력한다.

5. 이후 부스터 속력을 가지고 이분탐색을 진행해준다. 부스터 사용시간은 1초이므로 속력이 곧 이동한 거리가 된다.

(이동 거리 - 부스터 속력)을 자신의 속도로 나눈 값에 부스터 사용에 걸린 1초를 더한 값(완주하는 데 걸린 시간)이 vector[0]보다 작으면 부스터의 속도가 너무 빠른 것이므로 right=mid-1을 한다. 그 반대의 경우에는 left=mid+1을 한다.

6. 이분탐색이 끝나면 left를 출력한다. 자신이 완주하는데 걸린 시간이 vector[0]이랑 같아도 left에 1이 더해지므로(부스터 속력 증가) 자동으로 단독 우승이 가능해진다. 

 

주의할 점

변수 타입에 유의하자!

 

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	double t, n, x, y;
	cin >> t;

	while (t--) {
		cin >> n >> x >> y;
		vector<double>v;

		int speed;
		for (int i = 0; i < n; i++) {
			double a;
			cin >> a;

			double time = x / a;
			if (i == n - 1) {
				speed = a;
				break;
			}

			v.push_back(time);
		}

		sort(v.begin(), v.end());

		if (x / speed < v[0]) {
			cout << 0 << '\n';
			continue;
		}
		
		if ((x - y) / speed + 1 >= v[0]) {
			cout << -1 << '\n';
			continue;
		}

		int left = 0, right = y; //속력
		while (left <= right) {
			int mid = (left + right) / 2;

			if ((x-mid)/speed + 1 < v[0]) {
				right = mid - 1;
			}
			else {
				left = mid + 1;
			}
		}
		
		cout << left << '\n';
	}
}