POJ3977-Subset 折半枚舉

[SUMMER TRAIN] D1-B

題目位址 http://poj.org/problem?id=3977

題意: 輸入一個集合(n <= 35), 求出一子集使得此子集中所有元素的和的絕對值最小. 輸出和的絕對值與子集元素的數量.

• 無腦暴力O(2^n), 妥妥的t掉.

• 分成兩個子集 對每個子集暴力枚舉, 然後兩個子集進行比對.

  時間複雜度 O((log2(n/2))^2 * 2^(n/2)) 比1e6 大了一點點, 可以接受.

• 坑點:
  1. long long
  2. fabs()

#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;

int n, cnt;
long long in[], sum;
const long long INF = ;
map <long long, int> fst;
map <long long, int> lst;
map <long long, int> :: iterator itf;
map <long long, int> :: iterator itl;

long long labs(long long a) {
    return a >=  ? a : -a;
}
int mmin(int a, int b) {
    return a < b ? a : b;
}
long long mmin(long long a, long long b) {
    return a < b ? a : b;
}

int main() {
//  freopen("in.in", "r", stdin);
//  freopen("b.out", "w", stdout);
    while (scanf("%d", &n) ==  && n) {
        fst.clear(), lst.clear();
        sum = INF, cnt = ;

        for (int i = ; i < n; ++i)
            scanf("%lld", in+i);
        sort(in, in+n);
        long long ctmp = ((long long) << (int)(n/));
        for (long long i = ; i < ctmp; ++i) {
            long long tmp = ;
            int tcnt = ;
            for (int j = ; ; ++j) {
                if (!(i >> j)) break;
                if ((i >> j) & ) tmp += in[j], ++tcnt;
            }
            if (fst[tmp] == ) fst[tmp] = tcnt;
            else fst[tmp] = fst[tmp] < tcnt ? fst[tmp] : tcnt;
            if (labs(tmp) == sum) cnt = mmin(cnt, tcnt);
            else if (labs(tmp) < sum) cnt = tcnt, sum = labs(tmp);
        }
        for (long long i = ctmp; i < ((long long)<<n); i += ctmp) {
            long long tmp = ;
            int tcnt = ;
            for (int j = ; ; ++j) {
                if (!(i>>j)) break;
                if ((i>>j) & ) tmp += in[j], ++tcnt;
            }
            if (lst[tmp] == ) lst[tmp] = tcnt;
            else lst[tmp] = lst[tmp] < tcnt ? lst[tmp] : tcnt;
            if (labs(tmp) == sum) cnt = mmin(cnt, tcnt);
            else if (labs(tmp) < sum) cnt = tcnt, sum = labs(tmp);
        }

        for (itl = lst.begin(); itl != lst.end(); ++itl) {
            itf = fst.lower_bound(-(itl->first));   
            if (itf != fst.begin()) {
                --itf;
                if (labs(itf->first + itl->first) == sum)
                    cnt = mmin(itf->second + itl->second, cnt);
                else if (labs(itf->first + itl->first) < sum) {
                    sum = labs(itf->first + itl->first);
                    cnt = itf->second + itl->second;
                }
                ++itf;
            }
            if (itf == fst.end()) continue;
            if (labs(itf->first + itl->first) == sum)
                cnt = mmin(itf->second + itl->second, cnt);
            else if (labs(itf->first + itl->first) < sum) {
                sum = labs(itf->first + itl->first);
                cnt = itf->second + itl->second;
            }
        }
        printf ("%lld %d\n", sum, cnt);
    }
    return ;
}
/**********
**常數巨大**
***********/
           

1. 變量名巨醜無比而且較為混亂.
2. 初寫的時候沒有想到會寫這麼多行, 直接在主函數中進行處理, 可讀性–.
3. 細節錯誤不斷.