#Educational Codeforces Round 114 (Div.2) C - Slay the dragon

문제 링크 => Problem - C - Codeforces

Problem - C - Codeforces

---

 

sorting 을 이용한 binary search 문제이다.

 

문제에 대해 간략하게 설명하자면 다음과 같다.

 

영웅들 n명과 드래곤 1명이 주어지며 힘, 수비력은 다음과 같이 주어진다.

 

영웅 => 드래곤에 맞서 싸울 영웅 1명과 드래곤의 공격을 받아쳐낼 (n - 1)명의 영웅들이 존재한다.

            이때, 영웅의 각각 가지고 있는 힘을 ai 라고 한다. (1 <= i <= n)

 

드래곤 => 수비력 x 와 힘 y 가 존재한다.

 

m 명의 드래곤이 수비력 xi, 힘 yi (1 <= i <= m) 이 주어질 때, 영웅들이 드래곤의 공격을 받아낼 수

있어야 하며 또한 드래곤을 쓰러뜨릴 수 있도록 영웅의 힘을 최소한으로 끌어올리도록 하는 값을

찾아내야 한다. (m 개의 query에 대해서 독립적으로 수행함)

 

 

4가지 케이스가 존재한다.

 

1. 영웅들의 힘이 전부 드래곤의 수비력보다 크거나 같을 경우

 

=> 이 경우에는 가장 힘이 약한 영웅을 한명 보내고 나머지 영웅들을 드래곤의 공격을 받아쳐내야 한다.

    이때, 드래곤의 공격(y)이 나머지 영웅들의 힘(total)보다 클 경우 (y - total)만큼 힘을 키우면 된다.

    반면에 같거나 작을경우 힘을 키우지 않아도 된다. 

 

2. 영웅들의 힘이 전부 드래곤의 수비력보다 작을 경우

 

=> 드래곤의 수비력(x)이 높아서 무조건 영웅들의 힘을 키워서 맞서 싸우도록 해야 한다.

     이 경우에는 가장 힘이 높은 영웅(maxPower)을 (x - maxPower)만큼 힘을 키워서 보내야 한다.

     그리고 드래곤의 공격(y)이 나머지 영웅들의 힘(total)보다 클 경우 (y - total)만큼 힘을 키우면 된다.

     반면에 같거나 작을경우 힘을 키우지 않아도 된다.  

 

 

3. 특정 영웅의 힘이 드래곤의 수비력과 같을 경우

 

=> 해당 영웅을 한명 보내고 나머지 영웅들을 드래곤의 공격을 받아쳐내야 한다.

    드래곤의 공격(y)이 나머지 영웅들의 힘(total)보다 클 경우 (y - total)만큼 힘을 키우면 된다.

    반면에 같거나 작을경우 힘을 키우지 않아도 된다. 

 

4. 1, 2, 3 케이스 전부 해당하지 않는 경우

 

=> 이 경우가 가장 중요한 케이스인데 다음과 같은 예시가 주어진다고 가정하자.

 

 

ex ) 영웅의 힘 [1, 10, 20, 100] 이고 드래곤의 수비력 : 13, 힘 : 50  

 

이때 드래곤의 수비력에 가장 근접한 영웅의 힘은 10, 20 이 존재한다.

 

2번째 영웅(10)을 보낼 경우 =>  [10 + 3]   [1, 20, 100]   총 3 만큼 힘을 키우면 된다. 

 

3번째 영웅(20)을 보낼 경우 =>  [20]   [1, 10, 100]   힘을 키우지 않아도 된다.

 

 

그렇다면 드래곤의 수비력이 13이고 힘이 500 이라면? 

 

2번째 영웅(10)을 보낼 경우 =>  [10 + 3]   [1, 20, 100 + 379]   총 382 만큼 힘을 키우면 된다. 

 

3번째 영웅(20)을 보낼 경우 =>  [20]   [1, 10, 100 + 379]   총 389 만큼 힘을 키우면 된다.

 

 

결론 : lower_bound 를 통해서 영웅의 수비력과 근접한 힘을 가진 영웅 2명을 위 과정처럼

총 키워야 할 힘을 구하고 두 값을 비교하여 더 작은 값이 나올 경우 정답이 된다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <queue>
#include <stack>
#define endl '\n'
#define INF 1000000000
#define ll long long

using namespace std;

vector<ll> heroes;
ll heroTotal, maxHero, minHero;
int n, m;

void test(ll x, ll y) {

	int idx = lower_bound(heroes.begin(), heroes.end(), x) - heroes.begin();
	ll result = 0;

	if (idx == n) {
		result = x - maxHero;
		ll remain = heroTotal - maxHero;
		if (y > remain) result += y - remain;
	}
	else if (idx == 0) {
		ll remain = heroTotal - minHero;
		if (y > remain) result = y - remain;
	}
	else {
		if (heroes[idx] == x) {
			ll remain = heroTotal - heroes[idx];
			if (y > remain) result += y - remain;
		}
		else {
			ll tmpResult = 0;
			result = x - heroes[idx - 1];
			ll remain = heroTotal - heroes[idx - 1];
			if (y > remain) result += y - remain;

			tmpResult = (x - heroes[idx] < 0 ? 0 : x - heroes[idx]);
			remain = heroTotal - heroes[idx];
			if (y > remain) tmpResult += y - remain;

			cout << min(tmpResult, result) << endl;
			return;
		}
	}

	cout << result << endl;
}

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

	cin >> n;
	minHero = 1e12;

	for (int i = 0; i < n; i++) {
		ll x;
		cin >> x;
		heroes.push_back(x);
		heroTotal += x;
		maxHero = max(maxHero, x);
		minHero = min(minHero, x);
	}
	sort(heroes.begin(), heroes.end());

	cin >> m;
	for (int i = 0; i < m; i++) {
		ll x, y;
		cin >> x >> y;
		test(x, y);
	}

	return 0;
}