[Algo] 백준 예산 c++ // 매개변수 탐색

* 의사코드

• 먼저 함수를 정의하라.
• 0일때, 1일때 나눠서 st, en의 위치를 결정하라

• solve 함수를 작성하라.
  • min을 이용해서, 둘중 적은것을 누적하고, 그게 예산이하인지 확인하면 되는듯?
  • 예외케이스 고려할 필요없는듯 하다.

//배정예산 상한액이 x일때, 되는지
ll go(ll x) {
    if (x > m) return 0; //상한액이 총예산을 넘어가는 경우

    //모든 요청이 배정될수 있는경우
    if (sum <= m) {
        return 1;
    }
    ////배정될수없는경우
    ll tmp = 0;
    for (int i = 0; i < n; ++i) {
        if (arr[i] > x) tmp += x;
        else tmp += arr[i];
    }
    return tmp <= m;
}

//by 바킹독
bool solve(int uplim) {
  int sum = 0;
  for(int i = 0; i < n; i++)
    sum += min(a[i], uplim);
  return budget >= sum;
}

 

* 전체코드

• solve 부분만 제외하면 바킹독님 코드와 거의 일치
• 불필요한 sort 제거 필요

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m, sum;
ll arr[10004];
ll ret; //배정된 예산중 최대값

//배정예산 상한액이 x일때, 되는지
ll go(ll x) {
    if (x > m) return 0; //상한액이 총예산을 넘어가는 경우

    //모든 요청이 배정될수 있는경우
    if (sum <= m) {
        return 1;
    }
    ////배정될수없는경우
    ll tmp = 0;
    for (int i = 0; i < n; ++i) {
        if (arr[i] > x) tmp += x;
        else tmp += arr[i];
    }
    return tmp <= m;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        sum += arr[i];
    }
    cin >> m;

    sort(arr, arr + n);
    ll st = 1;
    ll en = *max_element(arr, arr+n);

    while (st < en) {
        ll mid = (st + en+1) / 2;
        //cout << st << " "<< mid<<" " << en << "\n";

        if (go(mid)) {
            st = mid;
        }
        else {
            en = mid - 1;
        }
    }

    cout << st;

    return 0;
}