分治法 - dblank

分治法

平面上的分支法

HDU 1007 Quoit Design

求平面上的最近两点距离。

可以先把点按照x坐标排序,然后将它们分成左右两个点集,这个时候的答案就是左边最小点距离还有右边最小点距离,以及两个点集最近的距离。

左右最小值可以通过递归求解,对于中间间隔点最小距离,一定是小于d的,我们可以枚举x坐标和y轴坐标相差小于d的点来更新。做到nlogn。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 100000 + 10, Mod = 1000000000;
typedef long long ll;
typedef pair<double, double> P;
P p[N], q[N];
double dis(P a, P b)
{
    return sqrt((a.first - b.first)*(a.first - b.first) +
                (a.second - b.second)*(a.second - b.second));
}
int cmp(P a, P b)
{
    return a.second < b.second;
}
double solve(int l, int r)
{
    if(l == r) return inf;
    if(r - l == 1) return dis(p[l], p[r]);
    int mid = (l+r)>>1, c = 0;
    double x = p[mid].first;
    double d = min(solve(l, mid), solve(mid+1, r));
    for(int i = l; i<=r; i++)
    {
        if(fabs(p[i].first - x) <= d)
            q[c++] = p[i];
    }
    sort(q, q+c, cmp);
    for(int i = 0; i<c; i++)
    {
        for(int j = i+1; j<c && q[j].second - q[i].second<d; j++)
        {
            double li = dis(q[j], q[i]);
            d = min(d, li);
        }
    }
    return d;
}
int main()
{
    int n;
    while(~scanf("%d", &n) && n)
    {
        for(int i = 0; i<n; i++)
            scanf("%lf%lf", &p[i].first, &p[i].second);
        sort(p, p+n);
        printf("%.2f\n", solve(0, n-1)/2);
    }
    return 0;
}

数列上的分治法

归并排序就是一种很好的分治思想,这个是将数列分成左右两个区间,直到长度唯一,这个层数是logn,然后我们对两个有序数列进行合并,这个复杂度是n,于是归并排序的复杂度是nlogn,可以利用这个特性,再进行归并排序的时候统计逆序对。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 100000 + 10, Mod = 1000000000;
typedef long long ll;
typedef pair<double, double> P;
typedef vector<int> V;
V a;
ll solve(V &amp;a)
{
    ll cnt = 0;
    int n = a.size();
    if(n<=1) return 0;
    V b(a.begin(), a.begin() + n/2);
    V c(a.begin() + n/2, a.end());
    cnt += solve(b);
    cnt += solve(c);
    int ai = 0, bi = 0, ci = 0;
    while(ai<n)
    {
        if(bi<b.size() &amp;&amp; (ci == c.size() || b[bi] <= c[ci]))
            a[ai++] = b[bi++];
        else
        {
            a[ai++] = c[ci++];
            cnt += n/2 - bi;
        }
    }
    return cnt;
}
int main()
{
    int n, x;
    while(~scanf("%d", &amp;n) &amp;&amp; n)
    {
        a.clear();
        for(int i = 0; i<n; i++)
            scanf("%d", &amp;x), a.push_back(x);
        printf("%lld\n", solve(a));
    }
    return 0;
}

发表新评论