首页 > 代码库 > 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^9K<=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

 

    贴上具体代码

    

技术分享
 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)