COFO::1443C The Delivery Dilemma

• Link : COFO::1443C

Problem A

• level : 1400
• tag : binary search, greedy, sortings

Point

• n이 주어집니다.
• n개로 이루어진 배열 a와 배열 b가 주어집니다.
• n개 중 원하는 갯수 k개를 정합니다.
• 배열 a에서 k개를 선택하고, 배열 b에서 n-k를 선택합니다.
• 이때 각 배열에서 고른 인덱스는 겹치면 안됩니다.
• S는 다음과 같습니다.
  • a에서 선택된 k개의 수 중 가장 큰 수를 A라고 합시다.
  • b에서 선택된 n-k개의 수의 합을 B라고 합시다.
  • 이때, S = max(A, B)입니다.
• 가장 작은 S를 출력합니다.

Design

• 방법이 2가지가 있지만 모두 같은 방법입니다.
  • 하나는 제가 푼 것처럼 discrete한 포인트를 a배열의 값으로 잡는 방법과
  • 다른 하나는 아무 값으로 잡는 방법입니다.
    • 이 방법이 바이너리 서치이며, 전자에 비해 이득보는 부분이 없고, 어차피 discrete한 주변 값을 찾아줘야해서 큰 이득이 없습니다.
• 문제 풀이는 다음과 같습니다.
  • a와 b를 짝을 지어두고 a값을 기준으로 정렬을 진행합니다.
  • 이때, i번째 과정에 대해 생각해봅시다.
  • a[i]가 선택되었습니다.
    • 그럼, 범위 [0:i-1]은 모두 무시해도 됩니다.
    • 모두 a를 선택했다고 가정할 수 있고, 이 경우 a[i]보다 모두 같거나 작은수이기 때문입니다.
    • 이제 [i+1:n-1]범위는 모두 b배열에서 선택해야 하므로 그 합을 미리 구해놓고 계산해주면 됩니다.

Big O(time)

• O(NlogN)

Big O(memory)

Code

// https://beenpow.github.io/
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define r_rep(i,a,b) for(int i=(a);i>(b);i--)
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
typedef long long ll;
using namespace std;
vector<pair<ll,ll> > v;
vector<ll> sum;

int n;
void input(){
    v.clear();
    cin >> n;
    v.resize(n);
    rep(i, 0, n) cin >> v[i].first;
    rep(i, 0, n) cin >> v[i].second;
    sort(v.begin(), v.end());
    
    sum.clear();
    sum.resize(n);
    sum[n-1] = v[n-1].second;
    r_rep(i, n-2, -1){
        sum[i] = v[i].second + sum[i+1];
    }
}

void solve(){
    input();
    ll mn = sum[0];
    rep(i, 0, n){
        ll r = max(v[i].first, i == n-1?0:sum[i+1]);
        if(mn > r)
            mn = r;
    }
    cout << mn << '\n';
}

int main(){
    int tc; cin >> tc;
    while(tc--)
        solve();
    return 0;
}