【題解】Codeforces 1413C. Perform Easily

【題目敘述】http://codeforces.com/contest/1413/problem/C

#include <bits/stdc++.h>
using namespace std;
 
int n, a[6], b[100005], cnt[100005];
vector <pair<int, int>> v;
 
int main(){
    for (int i = 0; i < 6; i++){
        cin >> a[i];
    }
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> b[i];
        for (int j = 0; j < 6; j++){
            v.push_back({b[i]-a[j], i});
        }
    }
    sort(v.begin(), v.end());
    int r = 0, k = 0, ans = 1e9;
    for (int i = 0; i < v.size(); i++){
        if (i){
            cnt[v[i-1].second]--;
            if (cnt[v[i-1].second] == 0) k--;
        }
        while (k < n && r < v.size()){
            if (cnt[v[r].second] == 0) k++;
            cnt[v[r].second]++;
            r++;
        }
        if (k == n) ans = min(ans, v[r-1].first-v[i].first);
    }
    cout << ans << "\n";
}
分享本文 Share with friends