[2512] 예산

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

이 문제는 각 나라에 배정할 예산을 탐색하면 됩니다.

조심할 점은 내가 탐색할 예산액보다 요구하는 양이 적은 지방은 다 주지말고 그냥 전체 예산액에서 빼줘야한다는 점과

더 많은 지방에는 예산액만큼만 줘야한다는 점입니다. 이 두개만 조심하면 쉬운 문제인 것 같습니다.

아 추가로.. 만약 각 지방이 요구하는 금액이 국가 에산보다 적을 시에는 그냥 요구하는 금액만큼 주면되므로 그 중 최대값을 출력하면됩니다.

아래의 코드입니다.

    for(int i = 0; i < n; i++)
    {
        tmp -= money[i];
        max_money = money[i] > max_money ? money[i] : max_money;
    }
 
    if(tmp >= 0) return printf("%d\n", max_money), 0;

#include <cstdio>
#include <algorithm>
#include <iostream>
 
#define MAX_SIZE 10000
#define INF 1e9
 
using namespace std;
 
int money[MAX_SIZE];
 
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &money[i]);
 
    int total;
    scanf("%d", &total);
 
    int tmp = total;
    int max_money = 0;
 
    for(int i = 0; i < n; i++)
    {
        tmp -= money[i];
        max_money = money[i] > max_money ? money[i] : max_money;
    }
 
    if(tmp >= 0) return printf("%d\n", max_money), 0;
 
    int left = total / n, right = max_money;
 
    while(left <= right)
    {
        int mid = (left + right) / 2;
        tmp = total;
 
        for(int i = 0; i < n; i++)
        {
            if(mid >= money[i]) tmp -= money[i];
            else tmp -= mid;
        }
 
        if(tmp >= 0) left = mid + 1;
        else right = mid - 1;
    }
 
    printf("%d\n", right);
 
    return 0;
}