POJ3977 Subset 折半枚举-白红宇

POJ3977 Subset 折半枚举

阅读量：7126 次

发布时间：2019-06-28

本文共 2200 字，大约阅读时间需要 7 分钟。

题目大意是给定N个数的集合，从这个集合中找到一个非空子集，使得该子集元素和的绝对值最小。假设有多个答案，输出元素个数最少的那个。

N最多为35，假设直接枚举显然是不行的。

可是假设我们将这些数分成两半后再枚举的话，最多有2^18(262144)，此时我们两半枚举后的结果进行排序后再二分搜索一下就能够了。复杂度为O(nlogn) n最多2^18。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               using namespace std;struct MyStruct{ long long res; int i;};int compp(const void* a1, const void* a2){ long long dif = ((MyStruct*)a1)->res - ((MyStruct*)a2)->res; if (dif > 0) { return 1; } else if (dif == 0) { return 0; } else return -1;}MyStruct res[2][300000];inline long long absll(long long X){ if (X < 0) { return X * (-1); } else return X;}int main(){ int n;#ifdef _DEBUG freopen("d:\\in.txt", "r", stdin);#endif long long values[36]; while (scanf("%d", &n) != EOF) { if (n == 0) { break; } for (int i = 0; i < n; i++) { scanf("%I64d", &values[i]); } int maxn = n - n / 2; int maxm = n - maxn; memset(res, 0, sizeof(res)); for (int i = 0; i < 1 << maxn; i++) { res[0][i].i = i; for (int k = 0; k < 19; k++) { if ((i >> k) & 1) { res[0][i].res += values[k]; } } } qsort(res[0], 1 << maxn, sizeof(MyStruct), compp); for (int i = 0; i < 1 << maxm; i++) { res[1][i].i = i; for (int k = 0; k < 19; k++) { if ((i >> k) & 1) { res[1][i].res += values[k + maxn]; } } } qsort(res[1], 1 << maxm, sizeof(MyStruct), compp); long long minvalue = 1000000000000000LL; int mink = 32; int l = 0; int r = (1 << maxm); for (int i = 0; i < 1 << maxn; i++) { l = 0; int curk = 0; for (int k = 0; k < maxn; k++) { if ((res[0][i].i >> k) & 1) { curk++; } } while (r - l > 1) { int mid = (l + r) / 2; long long sum = res[1][mid].res + res[0][i].res; if (sum > 0) { r = mid; } else l = mid; } l = l >= 1 ? l - 1 : l; for (int k = l; k < (1 << maxm);k++) { int curm = 0; for (int m = 0; m < maxm; m++) { if ((res[1][k].i >> m) & 1) { curm++; } } if (curm == 0 && curk == 0) { continue; } long long sum = res[1][k].res + res[0][i].res; if (absll(sum) < minvalue) { mink = curm + curk; minvalue = absll(sum); } else if (absll(sum) == minvalue) { mink = min(mink, curk + curm); } else if (sum > 0) { break; } } } printf("%I64d %d\n", minvalue, mink); } return 0;}

转载地址：http://imhel.baihongyu.com/

你可能感兴趣的文章