Time Limit: 1 SecMemory Limit: 128 MB
Submit: 780Solved: 404
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;
}
