天天看點
傳回

《挑戰程式設計競賽》3.2.4 常用技巧-折半枚舉 POJ2785 3977 2549POJ2785POJ3977POJ2549

POJ2785

http://poj.org/problem?id=2785

題意

輸入n，表示a b c d 四個集合都有n個元素。之後每行輸入4個集合中的一個元素。求這四個集合每個集合中拿出一個數相加等于0的組數。

思路

如果直接搜，複雜度為O(N^3)，時間不滿足要求。

折半搜尋比較适合，把4個數字分成兩份，分别兩兩求和，得到兩個長度n*n的一維數組，排序後比較進行比對即可。

另外這個題還可以用hash，具體參考：POJ2785 4 Values whose Sum is 0（哈希）

代碼 

Source Code

Problem:        User: liangrx06
Memory: K      Time: MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = ;

int n, m;
int a[][N];
int x[N*N], y[N*N];

int main(void)
{
    cin >> n;
    m = n*n;
    for (int i = ; i < n; i ++)
        for (int j = ; j < ; j ++)
            scanf("%d", &a[j][i]);
    for (int i = ; i < n; i ++)
        for (int j = ; j < n; j ++)
            x[i*n+j] = a[][i] + a[][j];
    for (int i = ; i < n; i ++)
        for (int j = ; j < n; j ++)
            y[i*n+j] = a[][i] + a[][j];
    sort(y, y+m);

    long long ans = ;
    for (int i = ; i < m; i ++)
        ans += (upper_bound(y, y+m, -x[i]) - lower_bound(y, y+m, -x[i]));
    printf("%lld\n", ans);

    return ;
}

POJ3977

http://poj.org/problem?id=3977

題意

給定N個整數(不超過10^15)組成的數列(N<=35)，從中選出一個子集，使得這個子集的所有元素的值的和的絕對值最小，如果有多組資料滿足的話，選擇子集元素最少的那個。

思路

如果單純的枚舉的話，這N個數分别有選和不選兩種，是以一共有2^35個子集。很明顯，會逾時，但是我們可以将這個整數數列分成兩半，可得每邊最多18個，如果分别進行枚舉的話，複雜度可以降到O((N/2)²)，即最多2^18，在可接受範圍内。然後枚舉其中一個子集，二分查找與他組成絕對值最小的子集。

具體的做法為：

兩個數組A和B分别表示前一半元素組成的和以及後一半元素組成的和，數組中的元素用pair<LL, int>表示，LL代表和，int代表幾個元素組成的和。對兩個數組分别進行排序（第一依據是和的大小，第二依據是元素個數），然後順序掃描數組，相同和的元素隻保留元素個數最小的那個。另外順便對數組内的元素進行搜尋尋找答案。
答案可能位于的另一種情況是前一半和後一半各取一部分元素組成的和，這就可以枚舉數組A，然後在數組B中二分查找其相反數，注意這裡用的比較函數與排序時的比較函數是不同的：排序時比較函數有兩個比較依據，而這裡查找時的比較函數隻依據和的值。再者，由于我們要找的是絕對值最小，這裡用lower_bound查到值（使總和非負但絕對值最小）之後，應該還要對其前一個值（使總和為負但絕對值最小）進行驗證。

盡管思路很清晰，實際做的過程中需要注意的地方卻有很多，主要見具體做法說明及代碼。這個題我大概WA了5次，最後一次WA犯的錯誤是INF值設定的太小，後來設定成了(1LL<<60)就沒問題了。

最後看了一下這個題的AC率，确實很低，大概百分之十幾，有的人甚至送出失敗十幾次。确實是細節決定成敗。

代碼 

Source Code

Problem:        User: liangrx06
Memory: K       Time: MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long LL;
typedef pair<LL, int> PR;

const int N = ;
const int M = (<<);
const LL INF = (L<<);

bool cmp(PR x, PR y)
{
    if (x.first != y.first)
        return x.first < y.first;
    return x.second < y.second;
}

bool cmpVal(PR x, PR y)
{
    return x.first < y.first;
}

LL llabs(LL x)
{
    return x >=  ? x : -x;
}

int n2, n[], m[];
LL a[N];
PR s[][M];

int main(void)
{
    while (cin >> n2 && n2)
    {
        for (int i = ; i < n2; i ++)
            scanf("%lld", &a[i]);

        PR ans = PR(INF, N+);
        n[] = n2/;
        n[] = n2-n2/;
        for (int j = ; j < ; j ++) {
            m[j] = ( << n[j]);
            for (int k = ; k < m[j]; k++) {
                s[j][k].first = s[j][k].second = ;
                for (int i = ; i < n[j]; i ++) {
                    if ((k>>i) & ) {
                        s[j][k].first += a[i + j*n[]];
                        s[j][k].second ++;
                    }
                }
            }
            sort(s[j]+, s[j]+m[j], cmp);
            int cnt = ;
            for (int k = ; k < m[j]; k++) {
                if (s[j][k].first != s[j][k-].first) {
                    s[j][cnt++] = s[j][k];
                    PR y(llabs(s[j][k].first), s[j][k].second);
                    if (cmp(y, ans)) ans = y;
                }
            }
            m[j] = cnt;
        }

        for (int k = ; k < m[]; k++) {
            PR y(-s[][k].first, s[][k].second);
            PR *x = lower_bound(s[]+, s[]+m[], y, cmpVal);
            for (int j = -; j <= ; j++) {
                if (x+j < s[]+ || x+j >= s[]+m[]) continue;
                y = PR(llabs((x+j)->first + s[][k].first), (x+j)->second + s[][k].second);
                if (cmp(y, ans)) ans = y;
            }
        }

        printf("%lld %d\n", ans.first, ans.second);
    }

    return ;
}

POJ2549

http://poj.org/problem?id=2549

題意

給你一個公式a+b+c=d，讓你在同一個集合（元素不同）内滿足該條件時d的最大值，注意a b c d均不同。

思路

網上折半搜尋的思路一般是将a+b+c=d拆分成 a+b=d-c，然後我沒敢再繼續看，就自己開始寫了。沒寫到寫出了一直TLE或者WA。

後來看了一下網上别人寫的代碼，感覺自己的也沒什麼錯誤啊。然後運作了一下别人的代碼，發現時間記憶體都是0！！！！！！（當然這個代碼我發現還有點bug，修改後時間大約十幾ms，一會附上代碼）

參考别人的代碼後我自己的折半搜尋代碼終于也修改成功了，結果我的資料是“Memory: 15344K Time: 719MS”，差距真心好大！！！

分析了一下，主要原因出在搜a+b上，人家代碼是線性O(N)的，我的最壞能達到O(N^N)，平均估計也得O(NlogN)吧。

不說了，上代碼。。。

代碼1（我的折半枚舉） 

Source Code

Problem:        User: liangrx06
Memory: K      Time: MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = ;
const int INF = ;

struct Sum {
    int i, j;
    int v;
};

bool cmp(Sum x, Sum y)
{
    return x.v < y.v;
}

int n, m;
int A[N];
Sum x[][N*N];

int main(void)
{
    while (cin >> n && n) {
        m = n*n;
        for (int i = ; i < n; i ++)
            scanf("%d", &A[i]);
        sort(A, A+n);
        for (int i = ; i < n; i ++) {
            for (int j = ; j < n; j ++) {
                int id = i*n+j;
                x[][id].i = x[][id].i = i;
                x[][id].j = x[][id].j = j;
                x[][id].v = A[i] + A[j];
                x[][id].v = A[i] - A[j];
            }
        }
        sort(x[], x[]+m, cmp);

        int ans = -INF;
        int a, b, c, d;
        for (int i = m-; i >= ; i --) {
            d = x[][i].i, c = x[][i].j;
            if (c == d) continue;
            Sum *lp = lower_bound(x[], x[]+m, x[][i], cmp);
            Sum *up = upper_bound(x[], x[]+m, x[][i], cmp);
            for (Sum *p = lp; p < up; p ++) {
                a = p->i, b = p->j;
                if (a == b || a == c || a == d || b == c || b == d)
                    continue;
                //printf("%d %d %d %d\n", A[a], A[b], A[c], A[d]);
                ans = A[d];
                break;
            }
            if (ans > -INF) break;
        }
        if (ans == -INF)
            printf("no solution\n");
        else
            printf("%d\n", ans);
    }

    return ;
}

代碼2（更優的折半枚舉） 

Source Code

Problem:        User: liangrx06
Memory: K        Time: MS
Language: C++       Result: Accepted
Source Code
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int inf=-;
int a[];
int main()
{
    int n;
    while(scanf("%d",&n)&&n)
    {
        for(int i=;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        n--;
        int ans=inf;
        for(int i=n;i>=;i--)
        {
            for(int j=n;j>=;j--)
            {
                if(i==j)
                    continue;
                int sum=a[i]-a[j];
                for(int l=,r=j-;l<r;)
                {
                    if(a[l]+a[r]==sum)
                    {
                        if (l != i && r != i) {
                            ans=a[i];
                            break;
                        }
                    }
                    if(a[l]+a[r]>sum)
                        r--;
                    else
                        l++;
                }
                if(ans!=inf)
                    break;
            }
            if(ans!=inf)
                break;
        }
        if(ans==inf)
            printf("no solution\n");
        else
            printf("%d\n",ans);
    }
    return ;
}
挑戰程式設計競賽 poj 折半枚舉
上一篇: Python-變量，運算表達式
下一篇: python項目-python完整項目

繼續閱讀