Algoogle

Algorithm for Programming Contest

PKU 3104 Drying

Category: PKU Tag: binary-search

Drying

問題概要


解法


時間を2分探索する.

コード


(3104.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#define rep(i,a) for(int i = 0;i < (a); i++)
using namespace std;

typedef long long ll;

int n, k;
int a[100010];

bool can(int t){
    ll cnt = 0;
    rep(i,n){
        int res = a[i] - t;
        if(res > 0) cnt += (res + k - 2) / (k - 1);
    }
    return cnt <= t;
}

int main(){
    cin >> n;
    int maxa = 0;
    rep(i,n){
        scanf("%d",a+i);
        if(maxa < a[i]) maxa = a[i];
    }
    cin >> k;
    if(k == 1){
        cout << maxa << endl;
        return 0;
    }
    int lb = 0, ub = 1000000100;
    while(lb + 1 < ub){
        int mid = (lb + ub) / 2;
        if(can(mid)) ub = mid;
        else lb = mid;
    }
    cout << ub << endl;
    return 0;
}

Comments