Perform Easily

Created by LXC on Wed Nov 1 11:07:39 2023

https://codeforces.com/problemset/problem/1413/C

ranting: 1900

tag: binary search, brute force, dp, implementation, sortings, two pointers

problem

一把吉他6根弦，假设有无限品。

现在弹奏i弦j品会得到$a_i+j$音符

现在给出$b_1, b_2, \cdots, b_n$共计n个音符，每个音符都可以在不同的弦品组合上演奏，弹奏的难易程度取决于所用品格的最大指数和最小指数之间的差值。这种差值越小，演奏就越容易。请确定最小的可能差值。

solution

每个$b_i$可以在6根弦上演奏。在第j根弦上演奏的品是$b_i-a_j$。也就是说每个$b_i$有6中可能的品。

我们需要找到一个品的范围$[l,r]$，使得每个$b_i$存在一个品属于这个范围，并且保证r-l最小。

我们将所有的6n个品由小到大排序，对于每个品得知道属于哪个音符。我们可以按照二元组$(b_i-a_j, i)$排序。

使用滑动窗口，维护窗口$[l,r]$，保证所有音符至少存在一个品在窗口内。这样的窗口就是合法的。我们取合法窗口的最小长度就是答案。

发现对于不合法窗口$[l,r]$，其子窗口也不合法。所以区间包含具有二段性。

我们可以固定窗口左端点l，寻找第一个合法的右端点r。对于l作为左端点其最小合法窗口长度就是r-l。

我们知道$[l,r]$是合法的，$[l,r-1]$是不合法的。在l变为l+1后，$[l+1,r-1]$是不合法的，$[l+1,r]$是未知的。所以最小合法区间$[l,r]$和$[l+1,r’]$，$r’\ge r$。由于窗口两端指针都只增不减，所以总时间复杂度是$O(n)$

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    vector<ll> a(6);
    for (auto& i : a)
        cin >> i;
    sort(a.begin(), a.end());
    int n;
    cin >> n;
    vector<pair<ll, ll>> b;
    vector<int> c(n);
    int cnt = 0;
    // set<ll> st;
    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        for (int j = 0; j < 6; j++) {
            b.emplace_back(x - a[j], i);
        }
    }
    sort(b.begin(), b.end());
    int sz = b.size();
    // for (auto [i, j] : b) {
    //     cout << i << " " << j << endl;
    // }
    ll ans = 1e9 + 7;
    for (int l = 0, r = 0; l < sz; l++) {
        while (cnt < n && r < sz) {
            if (++c[b[r++].second] == 1)
                cnt++;
        }
        // cout << l << ' ' << r << endl;
        if (cnt == n)
            ans = min(ans, b[r - 1].first - b[l].first);
        if (--c[b[l].second] == 0)
            cnt--;
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}