Manthan, Codefest 18 A. Packets(思维)
Manthan, Codefest 18 A. Packets(思维)
Ch_Zaqdt
发布于 2019-01-10 17:05:01
发布于 2019-01-10 17:05:01
题目链接：http://codeforces.com/contest/1037/problem/A
题意是给了n个金币，问最少需要多少个袋子来装这些金币，从而使得能用这些袋子凑成1-n的任意一个数字，比如6=1+2+3，7=1+2+4，只需要3个袋子就行。
思路就是因为要凑够1-n的所有数字，而且分最少的类，所以这个就类似多重背包的二进制优化(要尽量少的调用01背包)，详解可以去看这篇博客：多重背包的二进制优化(看第二段就好)。所以我们只需要求出2^k<=n,k取最大值再加1就好了，看了一眼Rank2的大神的code，真的是太强了...先上一个普遍的做法，再上大神的做法(直接输出二进制的最高位的位置)，其中所用的函数可以看下这篇博客：__builttin_函数。
AC代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
while(cin>>n){
int ans = 1;
int num = 0;
while(ans <= n){
ans *= 2;
num++;
}
cout<<num<<endl;
}
return 0;
}AC代码(思路惊奇)：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
cout<<32 - __builtin_clz(n)<<endl;
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年09月03日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读