Dreamoon Likes Coloring CodeForces - 1330C（贪心+思维）

本文主要是介绍Dreamoon Likes Coloring CodeForces - 1330C（贪心+思维），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Dreamoon likes coloring cells very much.

There is a row of n cells. Initially, all cells are empty (don’t contain any color). Cells are numbered from 1 to n.

You are given an integer m and m integers l1,l2,…,lm (1≤li≤n)

Dreamoon will perform m operations.

In i-th operation, Dreamoon will choose a number pi from range [1,n−li+1] (inclusive) and will paint all cells from pi to pi+li−1 (inclusive) in i-th color. Note that cells may be colored more one than once, in this case, cell will have the color from the latest operation.

Dreamoon hopes that after these m operations, all colors will appear at least once and all cells will be colored. Please help Dreamoon to choose pi in each operation to satisfy all constraints.

Input
The first line contains two integers n,m (1≤m≤n≤100000).

The second line contains m integers l1,l2,…,lm (1≤li≤n).

Output
If it’s impossible to perform m operations to satisfy all constraints, print “’-1” (without quotes).

Otherwise, print m integers p1,p2,…,pm (1≤pi≤n−li+1), after these m operations, all colors should appear at least once and all cells should be colored.

If there are several possible solutions, you can print any.

Examples
Input
5 3
3 2 2
Output
2 4 1
Input
10 1
1
Output
-1
思路：
首先考虑-1的情况：如果总共的长度小于n的话，肯定不行。如果对于其中的某一个元素a[i]，如果a[i]>n-i+1,这样也是不可以的。我们最贪心的考虑，第i个颜色是在i位开头，如果第i个颜色在第i位开头的话，长度超出了界限，那么它只能往前靠了。但是这样的话，就会覆盖前面的颜色了。如图所示：
在这里插入图片描述
④这条线就不符合了。
判断完-1的情况，那么就该考虑应该怎么贪心去放置这些颜色了。
如果第i个位置的颜色加上第i位之后颜色长度的总和（包括i）大于等于n的话，那么当前颜色要放置在i了，不能再往左靠了，可以往右靠，但是我们贪心的话，这样是最优的。如果上面的条件不符合的话，那就要尽量的往右靠，直到总和等于n就行。
代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxx=2e5+100;
int a[maxx];
int ans[maxx];
ll sum[maxx];
int n,m;inline int check()
{for(int i=1;i<=m;i++) if(a[i]>n-i+1) return 1;return 0;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) {scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];}if(sum[m]<n) cout<<-1<<endl;else if(check()) cout<<-1<<endl;else{int pos=0;for(int i=1;i<=m;i++){if(i+sum[m]-sum[i-1]-1>=n) ans[i]=i;else{int j=n-(sum[m]-sum[i-1]-1);//while(j+sum[m]-sum[i-1]-1<n) j++;ans[i]=j;}cout<<ans[i]<<" ";}cout<<endl;}return 0;
}