백준 2512 예산

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

2512번: 예산

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

using namespace std;



int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    int ans;

    cin >> n;

    vector<int> cost;

    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;

        cost.push_back(temp);
    }

    cin >> m;

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



    int s = 0;
    int e = cost[n - 1];
    int sum;


    while (s <= e) {
        sum=0;
        int mid = (s + e) / 2;

        for (int i = 0; i < n; i++) {
            sum += min(cost[i], mid);
        }
        if (m >= sum) {
            ans = mid;
            s = mid + 1;
        } else {
            e = mid - 1;
        }

    }

    cout << ans;

    return 0;
}

 

예산의 한도는 0원부터 각 지방 중 예산의 최댓값 중 찾을 수 있다.

예산을 정렬하고, 중간값을 예산의 한도로 정한 뒤, 그 때의 합을 구한다.

총 예산이 한도를 넘어가지 않으면 s=mid+1하여 예산의 한도를 높여보고, 

한도를 넘어간다면 e=mid-1하여 예산의 한도를 줄인다.