题目链接:http://www.bnuoj.com/v3/problem_show.php?pid=24252
这是四川2012年省赛的一道题，背景：海盗分宝藏。大概题意：给你N种价值的物品，物品有两个属性，一个是数量，一个是价值（价值是以2的ai次方表示的）。为了公平起见，求出宝藏分配的最小差（二进制表示）。
思路：当我们把宝藏合成后，即2*2^(n-1)宝藏=1*2^n宝藏（即二进制的进位处理），如果价值最大的宝藏可一分为二，那么该宝藏不会影响最终的结果（即该部分差值为0），如果价值最大的宝藏不可平分，那么必定结果必定是 该宝藏的价值-剩余宝藏的和 。（当进位处理后，差值最小的情况：2^n-(2^(n-2)+2^(n-2)+…+2^2+2^1)=1）。维护一个模拟二进制数组来记录宝藏的分布，比如a[2]=4表示2的2次方的宝藏有4个；然后进行进位处理，这时候我们需要一个标记数组，为什呢？因为当进位后如果某一位是1，这个1有两种情况：1>、这个1是进位得到的，那么它可以转换为比它低一位的2，比如：a[2]=1（进位的到），a[1]=0；这个时候相当于a[1]=2，即宝藏是可分的，不会影响结果。2>、这个1是本身就有的，那么则意味着该宝藏不可分，也就是找到可以得到答案的最大宝藏。很显然我们需要标记进位过程中哪一位的1是由进位得到的（这个过程很重要）。那么剩下的问题就是二进制的相减：题目中的减法很有特点，一定是1000000…(n个0)减去另一个二进制数，我们可以把这个二进制数转换为111111111…(n个1)+1；下面相减的过程就是一个简单的取反过程。代码如下
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <cstdlib> 5 #include <ctime> 6 #include <iostream> 7 #include <algorithm> 8 #include <vector> 9 #include <queue> 10 #include <map> 11 #include <set> 12 #include <string> 13 #define OUT(x) cout << #x << ": " << (x) << endl 14 using namespace std; 15 typedef long long LL; //注意要用long long存 16 const int maxn=100005; 17 const int INFF=999999999; 18 LL a[maxn]; 19 LL ans[maxn]; 20 bool fg[maxn]; 21 22 int main() 23 { 24 int T,i,cas=1; 25 scanf("%d",&T); 26 while(T--) 27 { 28 memset(a,0,sizeof a); 29 memset(fg,false,sizeof fg); 30 memset(ans,0,sizeof ans); 31 32 int n,val,num,max=0; 33 scanf("%d",&n); 34 for(i=0;i<n;i++) 35 { 36 scanf("%d %d",&val,&num); 37 if(max<val) //记录最大价值id 38 max=val; 39 a[val]+=num; 40 } 41 for(i=0;i<=max;i++) 42 { 43 if(a[i]>=2) 44 { 45 a[i+1]+=a[i]/2; //注意好顺序 46 a[i]%=2; 47 fg[i+1]=true; 48 } 49 } 50 51 int id=0; 52 for(i=max;i>0;i--) 53 { 54 if(a[i]%2 == 1&& !fg[i]) 55 { 56 id=i; 57 break; 58 } 59 } 60 printf("Case #%d: ",cas++); 61 if(id == 0) //判断 62 { 63 printf("%lld ",a[0]); 64 continue; 65 } 66 67 ans[0]=1; 68 for(i=id-1;i>=0;i--) 69 ans[i]+=(1-a[i]%2); 70 for(i=0;i<=id;i++) 71 if(ans[i]>=2) 72 { 73 ans[i]=0; 74 ans[i+1]++; 75 } 76 for(i=id+1;i>=0;i--) 77 { 78 if(ans[i] == 1) 79 break; 80 } //去除前导0 81 for(;i>=0;i--) 82 printf("%lld",ans[i]); 83 puts(""); 84 } 85 return 0; 86 }