10692 XYM-入门之道
时间限制:1000MS 内存限制:65535K提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC
Description
在华农的ACM界中，也有一对闻名古今的双胖师徒组合—XYM和BM. BM师父有一个特殊的癖好，BM肚子很大，因为他很
喜欢吃西瓜，但是BM的嘴很小，一次只能吃下大小不超过K的西瓜。刚进门的XYM为了能拜入BM大神的门下，他买来一个大
小为N的巨型西瓜请BM大神吃。但这个西瓜太大了，BM是不可能一次就吃完的，于是他让XYM将西瓜切开。为了简化问题，每切
一刀，大小为N的西瓜就为分成大小分别为N/2的两块小西瓜，如果N为奇数，则被分为一块大小为N/2，一块大小为（N/2 + 1）
的西瓜。（此处 “/” 为整除）
BM为了考验下XYM是否有资格成为他的徒弟，于是他就问XYM，这个大小为N的西瓜他一共要吃多少次才能全部吃完？
可是XYM要忙着切西瓜，于是他决定向你求助，你能帮他回答这个问题吗？
输入格式
第一行只有一个正整数T，表示题目共有T组数据
接下来一共有T行， 每行有两个正整数n, k，分别代表XYM买来的西瓜的大小和BM一次能吃下最大的西瓜的大小。
（输入数据保证n, k全部为正整数， 2<= n <=100000, 1<= k <= n-1）
输出格式
对于每组数据每行输出一个整数，代表BM一共要吃多少次才把整个西瓜全部吃完。
输入样例
3
14 3
15 1
1024 5
输出样例
6
15
256
提示
对于第一组数据：第一次切开后西瓜被分成两块大小为7的西瓜，对于每块大小为7的西瓜再切一刀就变成了一个大小为3和一块大小
为4的西瓜，大小为3的BM就能直接吃掉了，然后对于大小为4的西瓜再切一刀，就变成两块大小为2的西瓜。这时一共有6块西瓜，他
们的大小分别为2，2，2，2，3，3，所以BM一共要吃6次才能把西瓜全部吃完。
大水题；用一全局变量来统计切的次数，然后不断递归暴力二分下去直至西瓜的大小小于k为止，，1000ms绰绰有余。
1 #include <stdio.h>
2 int T;
3 long n,k,sum=
0;
4 void tree(
long a)
5 {
6 long t1=
0,t2=
0;
7 if(a<=
k)
8 sum++
;
9 else
10 {
11 if(a%
2==
0)
12 {
13 t1=t2=a/
2;
14 tree(t1);tree(t2);
15 }
16 else
17 {
18 t1=a/
2;t2=a/
2+
1;
19 tree(t1);tree(t2);
20 }
21 }
22 }
23 int main()
24 {
25 scanf(
"%d",&
T);
26 while(T>
0)
27 {
28 scanf(
"%ld%ld",&n,&
k);
29 tree(n);
30 printf(
"%ld\n",sum);
31 sum=
0;
32 T--
;
33 }
34 return 0;
35 }
转载于:https://www.cnblogs.com/geek1116/p/5243083.html
相关资源：数据结构—成绩单生成器
