Codeforces Round #526 (Div. 2) B. Kvass and the Fair Nut

B. Kvass and the Fair Nut

https://codeforces.com/contest/1084/problem/B

kvass는 러시아의 전통주고, keg는 술을 담는 커다란 통이다.

n개의 keg가 주어지고 각 keg별로 용량이 주어진다.

s리터만큼의 kvass를 확보해야 하는데, kvass를 확보한 후의 남은 kegs에서 가장 적은 용량을 가진 keg가 있을텐데,

그 용량이 최대가 되도록 kvass를 확보해야 한다.

해석이 잘 안되서 많이 헤맸던 문제인데, 해석만 되면 문제를 푸는 방법은 매우 간단하다.

먼저 주어진 keg들을 오름차순으로 정렬한다.

가장 적은 용량의 keg를 기준으로 각 keg에 들어있는 kvass의 용량은 어느정도인지 파악한다.

예를들면 4, 3, 5의 용량이 주어졌을 때, 3을 기준으로 용량을 파악하면 1, 0, 2가 될 것이다.

해당 용량이 s를 넘게 된다면 기준이 되었던 용량을 답으로 출력한다.

그게 아니라면 더 필요한 만큼을 전체 keg에서 1리터씩 추출한다고 생각하고, 이 작업을 몇번 해야 하는지 계산한다.

만약 4, 5, 6, 7, 8의 용량이 주어지고 s = 21이라고 할때, 0, 1, 2, 3, 4의 값을 더하면 10이고, 남은 용량은 11이다.

kegs의 개수는 5개이므로 한번의 작업당 5리터를 확보할 수 있게 되고, 가장 적은 용량은 1리터씩 줄어든다.

처음에 keg의 용량을 받을 때 전체의 합이 s보다 작다면 애초에 s를 채울 수 없으므로 -1을 출력하고 프로그램을 종료해주자.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { while (b) { a %= b, swap(a, b); }    return a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
#define MAXN 1050
#define PI 3.14159265358979323846
#define MOD 1000000000
 
ll n, m, k;
ll a, b, c, d;
ll s, arr[MAXN];
 
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> s;
    ll sumv = 0;
    for (int i = 0; i < n; i++) cin >> arr[i], sumv += arr[i];
    if (sumv < s) {
        cout << -1;
        return 0;
    }
    sort(arr, arr + n);
    sumv = 0;
    for (int i = 0; i < n; i++) sumv += arr[i] - arr[0];
 
    if (sumv > s) cout << arr[0];
    else {
        ll temp = arr[0] - (s - sumv + n - 1) / n;
        cout << temp;
    }
 
    return 0;
}