uva 11384 Help is needed for Dexter

时间:2020-12-08 20:59:43

https://vjudge.net/problem/UVA-11384

题意:

给出一个数n,任务是用最少的操作次数把序列1,2,3,。。。,n中所有的数都变成0。

每次操作可以从序列中选择一个或者多个整数,减去同一个相同的正整数。

输出最少的操作次数。

思路:

列了奇数和偶数的式子发现,每次减去最大值的(1 / 2) + 1,就可以使操作次数最少为log2(N) + 1,求对数的时候自己写函数来求。

直觉:)

代码:

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 int cal(long long n)
 5 {
 6     long long a = 1;
 7 
 8     int cnt = 0;
 9 
10     while (a <= n)
11     {
12         a <<= 1;
13         cnt++;
14     }
15 
16     return cnt - 1;
17 }
18 
19 int main()
20 {
21     long long n;
22 
23     while (scanf("%lld",&n) != EOF)
24     {
25         int ans = cal(n) + 1;
26 
27         printf("%d\n",ans);
28     }
29 
30     return 0;
31 }