[CF1329A] Dreamoon Likes Coloring - 构造

[CF1329A] Dreamoon Likes Coloring - 构造

Description

给定长为 \(n\) 的格子和 \(m\) 种颜色。Dreamoon 会依次刷这 \(m\) 种颜色，对于第 \(i\) 种颜色，他会从第 \(p_i\) 格开始刷到第 \(p_i+l_i-1\) 格。\(p_i\) 不能超过 \(n-l_i+1\) 或小于 \(1\)，这样会超出格子。您的任务是找出一组 \(p_i\)，使得 Dreamoon 刷完所有颜色之后每种颜色至少出现了一次，且每个格子都被刷上了颜色。

Solution

假设默认散开来放，同时记录一个剩余长度，如果剩余长度不够了，就压缩

#include 
using namespace std;

#define int long long

int n, m;
int l[100005], p[100005];

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> l[i];
    int res = 0;
    for (int i = 1; i <= m; i++)
        res += l[i];
    int pos = 1;
    for (int i = 1; i <= m; i++)
    {
        if (pos > n)
        {
            cout << -1;
            return 0;
        }
        p[i] = pos;
        res -= l[i];
        if (pos + l[i] > n + 1)
        {
            cout << -1;
            return 0;
        }
        pos += min(l[i], max(1ll, n - res - pos + 1));
    }
    if (pos != n + 1)
    {
        cout << -1 << endl;
        return 0;
    }
    else
    {
        for (int i = 1; i <= m; i++)
            cout << p[i] << " ";
        cout << endl;
    }
}