【題解】Kattis – Free Weights

【題目敘述】https://open.kattis.com/problems/freeweights
【解題想法】二分搜

#include <iostream>
using namespace std;

int n, a[1000005], b[1000005], mn, mx, now;

bool Check(int x){
    int pre = 0;
    for (int i = 0; i < n; i++){
        if (a[i] <= x) continue;
        if (!pre) pre = a[i];
        else if (a[i] != pre) return false;
        else pre = 0;
    }
    if (pre) return false;
    for (int i = 0; i < n; i++){
        if (b[i] <= x) continue;
        if (!pre) pre = b[i];
        else if (b[i] != pre) return false;
        else pre = 0;
    }
    if (pre) return false;
    return true;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    for (int i = 0; i < n; i++){
        cin >> b[i];
    }
    mn = -1;
    mx = 1e9;
    while (mx-mn > 1){
        int now = (mx+mn)/2;
        if (Check(now)) mx = now;
        else mn = now;
    }
    cout << mx << "\n";
}

分享本文 Share with friends