2016广东工业大学新生杯决赛 A-pigofzhou的巧克力棒

题目：GDUTOJ | pigofzhou的巧克力棒 (gdutcode.cn)

之前看了大佬博客的题解，一直没懂（我太菜了），后来听了朋友@77的讲解，终于懂了。

和拆分出2的n次方不一样，这是一种自下而上的方法。

从巧克力被全部折完开始，假设n==7，此时有7段长度为1的巧克力棒，我们试着向上还原，

于是可以把7段长度为1的巧克力棒两两合并为3段长度为2（还有1因为合并不了被舍弃了），这个过程就是7/2==3；

我们可以继续两两合并，把3段长度为2合并为1段长度为4，这个过程就是3/2==1；

所以答案就是3+1==4；

代码：

#include <iostream>

using namespace std;

typedef long long ll;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    ll t;

    cin >> t;

    while (t--)

    {

        ll n, ans = 0;

        cin >> n;

        while (n)

        {

            ans += n / 2;

            n /= 2;

        }

        cout << ans << endl;

    }

    return 0;

}

巴特西

2016广东工业大学新生杯决赛 A-pigofzhou的巧克力棒

最新文章

热门文章