1102: 正整数序列

Time Limit: 1 SecMemory Limit: 128 MB

Submit: 780Solved: 404

[Submit][Status][Web Board]

Description

给定正整数n,你的任务是用最少的操作数把序列1,2,3,...,n-1,n都变成0.每次操作可从序列中选择一个或多个整数,同时减去一个相同的正整数.比如1,2,3可以把2,3同时减去2,变成1,0,1.

Input

多组测试数据,每组仅一行,为正整数n.(1<=n<=10^9)

Output

对于每组数据输出最少的操作次数

Sample Input

1

2

3

Sample Output

1

2

2

zcmu1102 - ZP_nanfangguniang的博客 - CSDN博客

正整数序列-UVA 11384 - Help is needed for Dexter - 许佳佳的博客 - CSDN博客

找规律发现从中间开始分成两边，把大的那边同时减掉这样是最优的。设最少的步数为 f(n)，则答案为 f(n/2) + 1。

eg:(奇数)   1 2 3 4 5 6 7 8 9 -->(-5)----->1 2 3 4 0 1 2 3 4---->(-2)--->1 0 1 2 0 1 0 1 2  (再减两次)即9个数字==>4次--------n个数-->(int)(n/2)

(偶数)   1 2 3 4 5 6 7 8 9 10--->(-5)----->1 2 3 4 5 1 2 3 4 5---->(-3)---1 2 0 1 2 1 2 0 1 2  (减两次)即10个数字==>4次---------n个数-->(n/2)-1

---

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

int main(){

int a,b;

while(~scanf("%d",&a))

{

b=0;

while(a>0){

a/=2;

b++;

}

printf("%d\n",b);

}

return 0;

}