UVa 11384 Help is needed for Dexter 正整数序列

给定一个正整数 n ，你的任务使用最少的操作次数把序列 1, 2, 3, …… , n 中的所有数都变成 0 。每次操作可以从序列中选择一个或者多个数，同时减去一个相同的正整数。比如，1, 2, 3 可以把 2 和 3 同时减小 2 ，得到 1, 0, 1 。

模拟几次就能看出做法了。

例如当 n = 6 的时候

0      -----      1 2 3 4 5 6

1      -----      1 2 3 0 1 2

2      -----      1 0 1 0 1 0

3      -----      0 0 0 0 0 0

再比如 n = 9 的时候

0      -----      1 2 3 4 5 6 7 8 9

1      -----      1 2 3 4 0 1 2 3 4

2      -----      1 2 0 1 0 1 2 0 1

3      -----      1 0 0 1 0 1 0 0 1

4      -----      0 0 0 0 0 0 0 0 0

通过这两组例子就能很容易的看出，我每次都把原有数列分成两份，1 ~ len / 2 ，和 (len / 2) + 1 ~ len两部分。然后每次都减去 len / 2 这么多，然后 len = len / 2，如此循环，直到最后把 1 减去，所用的次数就是最小的次数。

现在知道怎么做了，就可以继续分析题目了。

按照上面的方法，我们可以得到下表：

1 ---- 1

2 ---- 2

3 ---- 2

4 ---- 3

5 ---- 3

6 ---- 3

7 ---- 3

8 ---- 4

打表打到这里，可以很轻松的看到规律。1 个 1 ， 2 个 2， 4 个 3 ， 8 个 4 。。。以此类推，规律就是这样了。然后写一个递归就能找到答案了。

附AC代码：

   1: #include <stdio.h>

   2: #include <math.h>

   3: #include <iostream>

   4: #include <cstdarg>

   5: #include <algorithm>

   6: #include <string.h>

   7: #include <stdlib.h>

   8: #include <string>

   9: #include <list>

  10: #include <vector>

  11: #include <map>

  12: #define LL long long

  13: #define M(a) memset(a, 0, sizeof(a))

  14: using namespace std;

15:

  16: void Clean(int count, ...)

  17: {

  18:     va_list arg_ptr;

  19:     va_start (arg_ptr, count);

  20:     for (int i = 0; i < count; i++)

  21:         M(va_arg(arg_ptr, int*));

  22:     va_end(arg_ptr);

  23: }

24:

  25: int res(int n)

  26: {

  27:     return (n == 1) ? 1 : res(n / 2) + 1;

  28: }

29:

  30: int main()

  31: {

  32:     int n;

  33:     while (cin >> n)

  34:         cout << res(n) << endl;

  35:     return 0;

  36: }

巴特西

UVa 11384 Help is needed for Dexter 正整数序列

最新文章

热门文章