codeforces #591 div2 C - Save the Nature (이분탐색)

모든 변수를 long long으로 바꿔주니 ac받았다.

 

 

배열크기n과 배열을 입력받고,

a번째 요소마다 x퍼센트의 기부금을 주는 것에 대한 입력 a,x,b,y를 입력받고,

기부금의 최소금액인 k를 입력받는다.

 

위와 같이 입력받은 후, k이상의 기부금을 받을 수 있는 최소한의 티켓수를 구하는 문제이다.

 

문제에서 배열의 순서를 자유롭게 할 수 있다고 한 것에 속아넘어가지 않고, 수학적으로 생각하면 된다.

 

조건에 맞는 티켓의 최소값을 찾는 이분탐색에 isPossible함수를 O(n)으로 구현해서 전체 O(logn)이다.

 

 

isPossible함수는 다음과 같이 구현했다. 팔리는 티켓수를 m이라고 할 떄, 

1) (x+y)%가 붙는 경우는 t = m/lcm(a,b)

2) x%가 붙는 경우는 r = m/a-t

3) y%가 붙는 경우는 s = m/b-t

 

내림차순 정렬된 입력받았던 배열에 순서대로 t,r,s경우를 적용해서 총 기부금의 합을 구한다.

 

이 총합이 k이상이라면 m은 가능한 경우이므로 isPossible은 true를 반환한다.

 

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

ll n, x, y, a, b;
ll k, arr[200001];

ll gcd(ll u, ll v) {
	if (v == 0) return u;
	return gcd(v, u % v);
}

ll lcm(ll u, ll v) {return u * v / gcd(u, v);}

bool isPossible(ll m) {
	ll t = m / lcm(a, b);
	ll r = m / a - t;
	ll s = m / b - t;

	ll sum=0;
	for (int i = 0; i < t; i++) 
		sum += arr[i] * (x + y) / 100;
	
	for (int i = t; i < r + t; i++) 
		sum += arr[i] * x / 100;
	
	for (int i = r + t; i < s + r + t; i++) 
		sum += arr[i] * y / 100;

	if (sum < k) return false;
	else return true;
}

int main() {
	int q; cin >> q;
	while (q--) {
		cin >> n;
		for (int i = 0; i < n; i++)
			cin >> arr[i];
		cin >> x >> a >> y >> b >> k;
		if (x < y) {
			swap(x, y);
			swap(a, b);
		}
		sort(arr, arr + n, [](ll p1, ll p2) {
			return p1 > p2;
		});

		ll lo = 1, hi = n + 1;
		while (lo < hi) {
			ll mid = (lo + hi) / 2;
			if (isPossible(mid)) hi = mid;
			else lo = mid + 1;
		}

		cout << (lo == n + 1 ? -1 : lo) << '\n';
	}
}