Codeforces Round #679 (Div. 2, based on Technocup 2021 Elimination Round 1) C. Perform Easily

C. Perform Easily

問題へのリンク

弾きたい曲の楽譜とギターの弦における音の下限が与えられるので、ギターの抑えるべき幅の最小値を求めよという問題。

ある区間の中に全ての音を包含するようにできるかを考えればいいが、これは尺取りでできる。

int main() {
    vector<int> a(6);
    cin >> a;
    int N;
    cin >> N;
    vector<int> b(N);
    cin >> b;
    vector<pair<int,int>> v;
    rep(i,N)rep(j,6){
        v.emplace_back(b[i]-a[j], i);
    }
    sort(all(v));
    int val = 0;
    vector<int> cnt(N, 0);
    int ans = INF;
    int M = 6 * N;
    for(int l = 0, r = 0; l < M; l++){
        while(r < M && val < N){
            int ridx = v[r].second;
            if(cnt[ridx] == 0)val++;
            cnt[ridx]++;
            r++;
        }
        if(val == N)chmin(ans, v[r-1].first - v[l].first);
        cnt[v[l].second]--;
        if(cnt[v[l].second] == 0)val--;
    }
    cout << ans << endl;
}