首页 > 代码库 > 2017广东工业大学程序设计竞赛 E倒水(Water)
2017广东工业大学程序设计竞赛 E倒水(Water)
原题链接:http://www.gdutcode.sinaapp.com/problem.php?cid=1057&pid=4
Problem E: 倒水(Water)
Description
一天，CC买了N个容量可以认为是无限大的瓶子，开始时每个瓶子里有1升水。接着~~CC发现瓶子实在太多了，于是他决定保留不超过K个瓶子。每次他选择两个当前含水量相同的瓶子，把一个瓶子的水全部倒进另一个里，然后把空瓶丢弃。(不能丢弃有水的瓶子)
显然在某些情况下CC无法达到目标，比如N=3,K=1。此时CC会重新买一些新的瓶子(新瓶子容量无限，开始时有1升水)，以到达目标。
现在CC想知道，最少需要买多少新瓶子才能达到目标呢？
Input
第一行一个整数T，表示有T组数据。
接着T行，每行两个正整数， N,K(1<=N<=10^9，K<=1000)。
Output
一个非负整数，表示最少需要买多少新瓶子。
Sample Input
3 3 1 13 2 1000000 5
Sample Output
1 3 15808
***********************************************************************************************
题意：
有n个瓶子，每个瓶子里有1升的水，当两个瓶子的水一样的时候，可以把2个瓶子合到一起，给了个k，还要加多少个瓶子才能够使总的瓶子合成不超过k个瓶子。
题解：
1） 我一开始想这一题毫无疑问是贪心，当出现奇数瓶子的时候就补上当前瓶子里的水（因为瓶子里的水就是n个1升水的个数）。然后发现第3个sample不对，算多了。
然后就突然想到，当出现奇数个瓶子的时候，把那一个瓶子拿到一边去（记录起来），剩下的两两合并。画了一下相对一种ans有减少。但是第3个样例不对。
最后发现我一开始把瓶子压到小于k的时候就停止了。其实还可以继续往下压缩，直到要缩到最后一个。（现在只有一个瓶子了）
在从记录起来的瓶子里从大到小补全k-1个瓶子（有k-1个瓶子了），把记录里面剩下的瓶子通过补充瓶子最后合并成一个瓶子。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <string> 6 #include <vector> 7 #include <map> 8 #include <set> 9 #include <queue> 10 #include <sstream> 11 #include <algorithm> 12 using namespace std; 13 #define pb push_back 14 #define mp make_pair 15 #define mset(a, b) memset((a), (b), sizeof(a)) 16 typedef long long LL; 17 const int inf = 0x3f3f3f3f; 18 const int maxn = 1000+10; 19 vector <int > hehe; 20 int solve(int n, int water) 21 { 22 if(n==1) return water; 23 if(n%2==0){ 24 solve(n/2, water*2); 25 } 26 else{ 27 hehe.pb(water); 28 solve((n-1)/2, water*2); 29 } 30 } 31 int main() 32 { 33 int T; 34 cin >> T; 35 while(T--) 36 { 37 int N, K; 38 cin >> N >> K; 39 if(N<=K) 40 cout << "0" << endl; 41 else 42 { 43 int endnum=solve(N, 1); 44 if(hehe.empty()){ 45 cout << "0" << endl; 46 } 47 else{ 48 int ans =0; 49 if(K==1){ 50 ans = endnum; 51 for(int i=0;i<hehe.size();i++) ans -= hehe[i]; 52 } 53 else 54 { 55 // for(int i =0 ;i< hehe.size();i++) cout <<hehe[i] <<endl; 56 int need = K -1; 57 if(need == 1){ 58 ans = hehe[hehe.size()-1]; 59 for(int i=0;i<hehe.size()-1;i++) ans -=hehe[i]; 60 } 61 else{ 62 ans = hehe[hehe.size() - need]; 63 for(int i=0;i<hehe.size()-need;i++) ans-=hehe[i]; 64 } 65 } 66 cout <<ans << endl; 67 } 68 } 69 hehe.clear(); 70 } 71 return 0; 72 }
2）官方题解:
看了一下题解，发现题解十分的巧妙。灵活运用 x&(-x) 和 n&=(n-1) ；
简单讲一下 x&(-x)是求 x 2进制时最低位的1的2^k的值，而n&=(n-1)是用来求 n 里有多少个1。
1 int cnt(int n){//计算n中有多少个1 2 int num=0; 3 while(n>0){ 4 num++; 5 n&=(n-1); 6 } 7 return num; 8 }
贴上具体代码
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <string> 6 #include <vector> 7 #include <map> 8 #include <set> 9 #include <queue> 10 #include <sstream> 11 #include <algorithm> 12 using namespace std; 13 #define pb push_back 14 #define mp make_pair 15 #define ms(a, b) memset((a), (b), sizeof(a)) 16 //#define LOCAL 17 typedef long long LL; 18 const int inf = 0x3f3f3f3f; 19 const int maxn = 10000+10; 20 const int mod = 1e9+7; 21 int cnt(int n){//计算n中有多少个1 22 int num=0; 23 while(n>0){ 24 num++; 25 n&=(n-1); 26 } 27 return num; 28 } 29 int lowbit(int x){ 30 return x&(-x); 31 } 32 int main() 33 { 34 #ifdef LOCAL 35 freopen("input.txt" , "r", stdin); 36 #endif // LOCAL 37 int T, n, k; 38 cin >> T; 39 while(T--){ 40 cin >> n >> k; 41 int ans =0; 42 while(cnt(n)>k){ 43 ans += lowbit(n); 44 n+=lowbit(n);//补上lowbit(n)个瓶子，就会进位。 45 } 46 cout << ans << endl; 47 } 48 return 0; 49 }
果然我还是太菜了XD。
2017广东工业大学程序设计竞赛 E倒水(Water)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。