Algoogle

Algorithm for Programming Contest

Codeforces 343C Read Time

Category: Codeforces Tag: binary-search

Read Time

問題概要


解法


かかる時間を二分探索する.
ある時間を決めて, その時間以下になるようにheadを動かしていく.
順にheadを見ていって, 左側にまだ読み取ってない場所があるならそれを読み取る.
そのとき時間オーバーなら失敗.
次にできるだけ右側を見ていく.
はじめ左側を見た場合、往復を挟むので順に右側を見ていく時の時間の比較は
はじめに右側を見たと仮定した場合も考慮する(どちらの往復のほうが得か考える).

コード


(343C.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
40
41
42
43
44
#include <bits/stdc++.h>
#define rep(i,a) for(int i = 0;i < (a); i++)
using namespace std;
typedef long long ll;
int n, m;
vector<ll> h, p;

bool can(ll tim){
    int cur = 0;
    rep(i,n){
        if(cur == m) break;
        ll t = p[cur];
        if(t >= h[i]){
            while(cur < m && p[cur] - h[i] <= tim) cur++;
        }
        else{
            if(h[i] - t > tim) return false;
            while(cur < m && p[cur] <= h[i]) cur++;
            while(cur < m && p[cur] - t + min(h[i] - t, p[cur] - h[i]) <= tim) cur++;
        }
    }
    return cur == m;
}

int main(){
    cin >> n >> m;
    h.resize(n); p.resize(m);
    rep(i,n) cin >> h[i];
    rep(i,m) cin >> p[i];

    if(m == 0){
        cout << 0 << endl;
        return 0;
    }

    ll lb = -1, ub = 20000000000;
    while(lb + 1 < ub){
        ll mid = (lb + ub) / 2;
        if(can(mid)) ub = mid;
        else lb = mid;
    }
    cout << ub << endl;
    return 0;
}

Comments