题目描述

blablabla

样例

blablabla

算法1

(greedy)

ps:参考题解
这题是一道标准的构造题，如果一道构造题叫你明确是否存在可能性(YES or No)，也许解决
这道题的第一件事就是发现无法实现该题的条件。
在这题有两个条件
case1:如果l的和小于n，那么n个格子是肯定染色不完的
case2:如果存在li + i -1 > n 那么至少有一种颜色会被第i种颜色覆盖
prove：假设前i-1种颜色l都只占1，那么当i颜色的l>n-i+1即从i开始染色格子超过了n
那么为了满足不超过n，必须左移则覆盖了前一种颜色。

满足了这两个条件后，是贪心。可以这么想，为了让所有颜色都有，我们尽量让颜色占有较少的
格子，但又害怕染色完后染色格子小于n。我们可以倒着做，如果从i开始染色不满足染色格子>n
即li+i-1<n,那么就右移到n，此时的点给记录下来。如果满足=n则该点即为i。接着n点变成上
一个染色操作的头。这样就一定能输出对。

时间复杂度

C++ 代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int M = 100010;
int l[M];
int res[M];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);

    ll sum = 0;
    for(int i = 1; i <= m; i++) {
        scanf("%d", &l[i]);
        sum += l[i];
    }

    if(sum < n) return 0 * printf("-1\n");
    for(int i = 1; i <= m; i++) {
        res[i] = i;
        if(i + l[i] - 1 > n) return 0 * printf("-1\n");
    }
    int last = n;
    for(int i = m; i >= 1; i--) {
        if(i + l[i] - 1 < last) {
            res[i] = last - l[i] + 1;
            last = res[i] - 1;
        } 
        else break;
    }

    for(int i = 1; i <= m; i++) printf("%d%c", res[i], " \n"[i == m]);
    return 0;
}