[codeforce] #526(Div. 2) B. Kvass and the Fair Nut

문제 링크 : http://codeforces.com/contest/1084/problem/B

문제 정리

• n 개의 서로 다른 양의 물(vL)을 가지고 있는 물통이 있다
• 철수는 sL를 담을 수 있는 물컵이 있다
• 여기서 서로 다른 양의 물통 중, 가장 적은 물통의 양을 최대로 하는 방법을 구하라.

문제 풀이

3개의 물에 5 / 3 / 4 리터가 있다고 가정하자. 

여기서 가장 적은 물의 양은 3 리터이다. 가장 적은 물의 양을 제외하고 나머지 물의 양을 받으면 

받은 물의 양 = (5 - 3) + (5 - 4) = 3 리터이다. 

if ( 받은 물의 양 >= 물컵의 양 ) 이면, 정답은 3리터이지만,

아닌 경우,

현재 물통의 상황은 3 / 3 / 3 이럴 것이다. 

여기서 한개의 물통에서 1리터만 빼어도 가장 적은 물은 2리터이다. 따라서, 총 N개를 모두 따라도 적은 물통은 2리터.

즉, N 리터씩 따르면서 물컵의 양과 비교하며 답을 구할 수 있다.

 

#include <iostream>

#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n;
	long long s;
	cin >> n >> s;
	vector<long long> a(n);
	long long temp = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		temp += a[i];
	}
	if (temp < s)
		cout << -1 << endl;
	else {
		sort(a.begin(), a.end());
		long long small = a[0];
		long long ret = 0;
		for (int i = 0; i < n; i++) {
			if (small != a[i]) {
				ret += a[i] - small;
			}
		}

		if (ret >= s) {
			cout << small << endl;
		}
		else {
			for (int k = small - 1; k >= 0; k--) {
				ret = ret + n;
				if (ret >= s) {
					cout << k << endl;
					break;
				}
			}
		}
	}
	return 0;
}