Dreamoon Likes Coloring 【CF 1329 A】

传送门

思路：“Dreamoon will choose a number pipi from range [1,n−li+1](inclusive) and will paint all cells from pipi to pi+li−1(inclusive) in ii-th color.”可以知道从[1, n - li - 1]任意位置往后染pi个格子为第ith种颜色。

容易想到，如果∑li < n，说明"-1"。

如果∑li>=n，因为我们不知道怎么染色才好，但我们知道SUM = ∑li，即我们目前还可以染色SUM块。不如我们类贪心的思想染色，这样我们可以分成两种情况:

假设now为当前的pi，len为剩余未染色的块

①SUM - now >= len - 1

说明我们只用当前颜色染色1块，之后SUM-now的个数也可以染色剩余的部分，那么 SUM -= now ，n -= 1

②SUM - now < len - 1

说明我们如果用当前颜色只染色1块，则SUM - now 不能染色剩余的 len - 1，那么我们需要让

SUM - now == len - 1 - ? (==>) ? = (len - 1) - (SUM - now),则当前颜色需要染色 ? + 1个才行。

这样我们可以用pre_s，pre_d记录之前的开始位置和染色长度。

当然我们不能忘记一个条件“每种颜色只能在[1, n - li - 1]开始往后染色”，如果（n - li - 1） < pre_s + pre_d，

说明我们无法完成满足题意的染色，因为我们前面是尽可能少的染色切满足题目要求，如果仍然无法满足，说明没有可行解。

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <algorithm>

 4 #include <cstring>

 5 #include <cmath>

 6 #include <queue>

 7 #include <vector>

 8 #include <cstring>

 9 #include <functional>

10 #define LL long long

11 using namespace std;

12

13 const int N = 1e5 + 10;

14 int L[N], inx[N];

15

16 void solve ()

17 {

18     int n, m, len;

19     scanf("%d%d", &n, &m);

20

21     LL Sum_d = 0;

22     for(int i = 1; i <= m; ++i) {

23         scanf("%d", L + i);

24         Sum_d += L[i];

25     }

26

27     int pre_s, pre_d;

28     pre_s = 1; pre_d = 0;

29     len = n;

30     for(int i = 1; i <= m; ++i) {

31         //printf("start = %d  L = %d\n", pre_s + pre_d, n - L[i] + 1);

32         if(n - L[i] + 1 < pre_s + pre_d) { break; }

33

34         if(Sum_d - L[i] >= len - 1) {

35             Sum_d -= L[i];

36             len -= 1;

37             pre_s = pre_s + pre_d;

38             pre_d = 1;

39         } else {

40             int tmp_d = (len - 1) - (Sum_d - L[i]);

41             if(tmp_d + 1 > L[i]) { break; }

42             Sum_d -= L[i];

43             len -= (1 + tmp_d);

44             pre_s = pre_s + pre_d;

45             pre_d = (1 + tmp_d);

46         }

47         inx[i] = pre_s;

48     }

49

50    // cout << "len = " << len << endl;

51

52     if(len > 0) {

53         printf("-1\n");

54     } else{

55         for(int i = 1; i <= m; ++i) { printf("%d ", inx[i]); }

56         printf("\n");

57     }

58

59

60 }

61

62 int main()

63 {

64     solve();

65

66     return 0;

67 }

巴特西

Dreamoon Likes Coloring 【CF 1329 A】

最新文章

热门文章