Poj 3977 Subset 折半枚举超大背包-白红宇

Poj 3977 Subset 折半枚举超大背包

阅读量：4112 次

发布时间：2019-05-25

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

题意：从一个集合（有正有负）里挑选若干个数字（数字个数不能为0），求挑选出来的数字的和的绝对值的最小值，数字个数<=35,数据范围<=10^15

注意事项：注意这道题的数据范围和对空集的处理，且运用了离散化的思想

AC代码：

#include 
     
       #include
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include
             #include 
             
               #include 
              
                using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const long long inf = 1e17; struct Node{ ll v, l; }; Node node1[3000000], node2[3000000],nod[3000000]; ll a[40]; ll absx(ll a) { return a > 0 ? a : -a; } bool cmp(Node a, Node b) { if(a.v!= b.v) return a.v
               
                1) { ll mid = (l + r) >> 1; if (nod[mid].v >= m) r = mid; else l = mid; } return r; } int main() { ll n; while (~scanf("%lld", &n)&&n) { for (ll i = 1; i <= n; i++) scanf("%lld", &a[i]); ll n1 = n / 2,n2=n-n1,minn = inf, mlen = 40;; ll cnt1 = (1<
                
                 temp) { minn=temp; mlen=node1[i].l; } else if(minn==temp&&mlen>node1[i].l) mlen=node1[i].l; } for (ll i = 1; i <=cnt2; i++) { node2[i].v = node2[i].l = 0; for (ll j = 0; j <=n2-1; j++) if (i&(1<
                 
                  temp) { minn=temp; mlen=node2[i].l; } else if(minn==temp&&mlen>node2[i].l) mlen=node2[i].l; } sort(node2 + 1,node2 +cnt2+1, cmp); nod[1].v=node2[1].v; nod[1].l=node2[1].l; ll p=1; for(ll i=2;i<=cnt2;i++) if(node2[i].v!=nod[p].v) { ++p; nod[p].v=node2[i].v; nod[p].l=node2[i].l; } for (ll i = 1; i <=cnt1; i++) { ll m = node1[i].v; ll j = binary(-m,p); if (absx(m + nod[j].v)
                  
                   node1[i].l + nod[j].l) mlen = node1[i].l + nod[j].l; j--; if(j==0) continue; if (absx(m + nod[j].v)
                   
                    node1[i].l + nod[j].l) mlen = node1[i].l + nod[j].l; } printf("%lld %lld\n", minn, mlen); } return 0; }

第一次wa代码：

#include 
     
       #include
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include
             #include 
             
               #include 
              
                using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int inf = 0x3f3f3f3f; struct Node{ ll v, l; }; Node node1[3000000], node2[3000000]; int a[40]; ll absx(ll a) { return a > 0 ? a : -a; } bool cmp(Node a, Node b) { return a.v < b.v; } ll binary(int m, int n) { ll l = 0, r = n; while (r - l>1) { ll mid = (l + r) >> 1; if (node2[mid].v >= m) r = mid; else l = mid; } return r; } int main() { ll n; while (~scanf("%lld", &n)&&n) { for (ll i = 1; i <= n; i++) scanf("%lld", &a[i]); ll n1 = n / 2,n2=n-n1; ll cnt1 = (1<
               
                node1[i].l + node2[j].l) mlen = node2[i].l + node2[j].l; j--; if (absx(m + node2[j].v)
                
                 node1[i].l + node2[j].l) mlen = node2[i].l + node2[j].l; } printf("%lld %lld\n", minn, mlen); } return 0; }