Dreamoon Likes Coloring

Created by LXC on Sat Apr 13 19:23:55 2024

https://codeforces.com/problemset/problem/1329/A

ranting: 1800

tag: constructive algorithms, greedy, implementation, math

problem

给定长为 $n$ 的格子和 $m$ 种颜色。

Dreamoon 会依次刷这 $m$ 种颜色，对于第 $i$ 种颜色，他会从第 $p_i$ 格开始刷到第 $p_i+l_i-1$ 格。$p_i$ 不能超过 $n-l_i+1$ 或小于 $1$，这样会超出格子。

您的任务是找出一组 $p_i$，使得 Dreamoon 刷完所有颜色之后每种颜色至少出现了一次，且每个格子都被刷上了颜色。

$1 \leq m \leq n \leq 10^5$，$1 \leq l_i \leq n$

翻译 by Meatherm

solution

如果$\sum l_i < n$说明不可能把所有格子刷满。

当我们刷第i个颜色时，在左侧预留了i-1个格子刷上了不同的颜色，如果此时$i-1+l_i > n$说明第i个颜色必定会覆盖前方i-1种颜色的至少一种，无法保证同时存在i种颜色。

现在为了确保刷第i种颜色时右边界不会超出n，我们采用逆向构造，先刷第m种颜色，然后刷m-1种颜色。。。第m种颜色的位置是$n-l_m+1$，然后我们知道左侧有$n-l_m$个位置，必须存在$m-1$种颜色，于是有$n-l_m-(m-l)$个空位可以任意刷颜色。

第i种颜色和第i+1种颜色之间最多能存在$l_i-1$个空位，与剩余的空位取最小值，在确定第i+1种颜色的起始位置下，第i种颜色的起始位置可以通过空位个数计算得出。

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;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    ll n, m;
    cin >> n >> m;
    vector<ll> a(m);
    ll s = 0;
    for (ll& i:a) cin >> i, s+=i;
    int ok = (s>=n);
    for (int i=0; i<m; i++) {
        if (i+a[i] > n) ok = 0;
    }
    if (!ok) {
        cout << "-1\n";
    } else {
        // n-a[m-1] need m-1, n-a[m-1]-(m-1)
        vector<int> ans;
        ans.push_back(n-a[m-1]+1);
        ll r = n-a[m-1]-(m-1);
        for (int p = m-2;p>=0; p--) {
            ll sub = min(r, a[p]-1);
            r -= sub;
            ans.push_back(ans.back()-sub-1);
        }
        reverse(ans.begin(), ans.end());
        // cout << ans << "\n";
        // for (int i=0; i<m; i++) {
        //     cout << i << " " << ans[i] << " " << ans[i]+a[i]-1 << "\n";
        // }
        for (int i:ans) {
            cout << i << " ";
        }
        cout << "\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;
}