20/04/08 USACO 유사코 1월 실버

실버가 3문제인데 2문제가 이분 탐색이었다. 이분 탐색을 참 좋아하는 거 같다.

Berry Picking, 18319

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

18319번: Berry Picking

$N$개의 나무에 $(1 \le N \le 1000)$ 열매들이 $B_i$개씩 열려 있다. $(1\le B\le 1000)$

$K$개의 바구니에 베리를 따 넣을 건데 하나의 바구니에는 한 나무에서 나온 베리들만 담을 수 있다.$(1\le K\le1000)$

(한 나무에서 나온 베리들을 여러 바구니에 나눠 담는 건 가능)

짝수개인 $K$개의 바구니 중 열매가 많이 담긴 $K/2$개의 바구니는 동생에게 줘야 한다. 이렇게 주고 남은 베리의 수를 최대로 하여라

범위가 1000이니 완전탐색을 하였다. 

14줄부터 나오는 i는 최대로 딸 수 있는 열매의 개수이다. 모든 나무에서 i개씩 열매를 따고 남는 것들은 우선순위 큐 v에 넣어준다. i개씩 딴 횟수를 ge라고 할 때 ge $\ge$ K이면 내가 가질 수 있는 최고의 열매수는 $i * \frac{K}{2}$개 이고 

ge $\ge \frac{K}{2}$ 이면 ge $- \frac{K}{2}$개 와 우선순위 큐 v상위 $K - $ge개의 합이 정답이 된다. 

ge $\lt \frac{K}{2}$의 경우는 해당 i보다 작은 값에서 얻은 정답을 얻을 수 있다.

 
vector<int> tree;
int ans = 0;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int tem;
        cin >> tem;
        tree.push_back(tem);
    }
    for (int i = 1; i <= 1000; i++) {
        priority_queue<int> v;
        int ge = 0;
        for (int j = 0; j < n; j++) {
            ge += tree[j] / i;
            v.push(tree[j] - tree[j] / i * i);
            if (ge > k)break;
        }
        
        if (ge >= k) {
            ans = max(ans, i * k / 2);
        }
        else if (ge >= k / 2) {
            int tem = 0;
            for (int j = 0; j < k - ge; j++) {
                tem += v.top();
                v.pop();
            }
            ans = max(ans, i * (ge - k / 2) + tem);
        }
    }
    cout << ans;
}

 

Loan Repayment, 18320

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

18320번: Loan Repayment

 

$K$일 동안 $N$개의 우유를 갚아야 한다. $(1 \le N \le 10^{12})$

단 최소 $M$씩은 갚아야 한다. $(1 \le M \le 10^{12})$ 

양수 $X$를 정해 갚을 껀데  $(1 \le X \le 10^{12})$ 갚아야 될 남은 우유를 $X$로 나눠 그 몫을 갚는다.

당연히 $M$이하면 M을 갚아야 한다. 이 때 $K$일이 될 때 딱 다 갚고 싶어 한다. 

$X$의 최대값을 찾는 문제이다. 

 

아주 간단한 이분탐색 문제처럼 보이고 생각 없이 휘리릭 쳐버리면 TL이 난다...

ll fun(ll a) {
    ll cou = 0;
    ll tN = N;
    while (tN) {
        cou++;
        ll tem =tN / a;
        if (tem < M) {
            tem = M;
        }
        tN -= tem;
        if (tN < 0)
            break;
    }
    return cou > K;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N >> K >> M;
    ll l = 1,r=1000000000000;
    while (l <= r) {
        ll mid = (l + r) / 2;
        if (fun(mid))
            r = mid - 1;
        else
            l = mid + 1;
    }
    cout << r;
}

fun 부분에서 시간초과 발생 

 

해당 문제를 고치기 위해선 중복되는 경우를 수식으로 풀어야 한다.

해당 내용이 12번째 줄이다. 

ll N, K, M;
 
bool fun(ll rest,ll day, ll a) {//rest: 남은 우유, day: 남은 날짜, a: 문제의 X
    ll tem = rest / a;//뺄 길이
    if (tem <= M) {//앞으로 다 M씩 갚아야 함
        return day * M >= rest;
    }
    if (tem * day < rest) //갚아나갈 tem은 증가 하지 않는데 해당조건 만족 못하면 불가능
        return false;
    if (rest <= 0 )//더 갚는건 
        return true;
    ll time = (rest - tem * a) / tem + 1;//나머지에서 뺼길이 만큼 있으면  한번에 빼도 됨 day가 음수면 걸러짐
    return fun(rest - time * tem, day - time, a);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N >> K >> M;
    ll l = 1,r=K+1;
    while (l <= r) {
        ll mid = (l + r) / 2;
        if (!fun(N,K,mid))
            r = mid - 1;
        else
            l = mid + 1;
    }
    cout << r;
}

Wormhole Sort, 18321

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

18321번: Wormhole Sort

문제를 읽다보면 제대로 해석하고 있는 게 맞는가 생각이 드는 문제

 $N$마리의 소를 $M$개의 웜홀을 사용해 알맞은 자리로 돌아가게 해 주면 되는 문제이다. $(1 \le N, M \le 10^{5})$

이때 사용한 웜홀의 넓이의 최소값이 최대가 되게 해야 한다.

단 윔홀의 넓이 $w_i$의 범위가 $(1 \le w_i \le 10^{9})$ 길어 $w_i$로 이분 탐색을 해줘야 한다.

이분탐색을 해야 한다는 것을 이전 문제보다 쉽게 풀 수 있다. 

단 웜홀의 끝인 $a_i, b_i$의 범위가 N의 범위와 같기 때문에 2차원 배열로 연결을 나타내면 안 되고 vector<pair<int,int>> adj[MAXN] 혹은 vector<Edge*> adj[MAXN];를 사용 해야 한다. 

int N, M;
int arr[MAXN];
int vis[MAXN];
 
struct Edge {
    int to, c;
    Edge(): Edge(-1, 0) {}
    Edge(int to1, int c1) : to(to1), c(c1) {}
};
vector<Edge*> adj[MAXN];
vector<int> v;
 
void dfs(int node,int worm,int che) {//node: 목장위치 , worm : 웜홀 최소 크기, che: 이번방문 
    vis[node] = che;
    if (node != arr[node])
        v.push_back(arr[node]);
    for (auto A : adj[node]) {
        int there = A->to;
        int siz = A->c;
        if (siz < worm)
            continue;
        if (vis[there] == 0)
            dfs(there, worm, che);
    }
}
bool fun(int a) {//이분탐색시 가능 불가능 판별
    for (int i = 1; i <= N; i++)vis[i] = 0;//초기화 
    for (int i = 1; i <= N; i++) {
        if (vis[i] == 0 && arr[i] != i) {// 방문한 적이 없고 소가 제자리에 있지 않을때
            v.clear();
            dfs(i,a,i);//dfs를 통해 방문한 목장을 다 i로 체크해주고 만난 제자리가 아닌 소들을 v에 넣어준다.
            for (int a : v) {//소들이 돌아가야 할 목장을 이번 dfs때 방문 하지 못했다면 그 소는 돌아 갈 수 없다. 
                if (vis[a] != i)
                    return false;
            }
        }
    }
//모든 소가 돌아갈 수 있다.
    return true;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N >> M;
    bool che = 0;
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        if (arr[i] != i)
            che = 1;
    }
    for (int i = 1; i <= M; i++) {//간선 입력
        int a, b, c;
        cin >> a >> b >> c;
        Edge* e1 = new Edge(b, c), * e2 = new Edge(a, c);
        adj[a].push_back(e1);
        adj[b].push_back(e2);
    }
    if (che == 0) {//필요가 없을경우 
        cout << -1;
        return 0;
    }
    int l = 1;
    int r = 1000'000'000;
    while (l <= r) {
        int mid = (l + r) / 2;//웜홀의 최소 넓이
        if (!fun(mid))
            r = mid - 1;
        else
            l = mid + 1;
    }
    cout << r;
}