2013-11-09 19:57:28Morris

[ZJ][D&C] d847 2D rank finding problem

內容 :

二度空間上的排名計算問題(2D rank finding problem):給定二度平面空間(2D)上的點A = (a1,a2)與點B = (b1,b2),其大小關係定義A > B 若且唯若 a1> b1 a2 > b2 ;亦即A點在B點的右上方。如下圖中,B >A, C>A, D>A, D>C, D> B。值得注意的是,並非任意兩點均可以決定大小關係,如下圖中的點A與點E,點D與點E等,無法決定這兩點的大小關係故為無法比較(incomparable)。給定N個點(x1,y1), (x2,y2), …, (xn,yn),定義某一個點的排名(rank) 為所給的點集合中,比該點小的點的個數。


如上圖中,rank(A)= 0, rank(B) = 1, rank(C) = 1, rank(D) = 3, rank(E) = 0

設計一個程式,從檔案讀取點的名稱與座標,計算出在所給定的集合中,所有點的排名值。

輸入說明 :

有多組測試資料

每組的第一行有一個數字N ( 1 ≦ N ≦ 10000 )

接下來會有N行,每行上會有兩個數字  x  y  ( 1 ≦ x , y ≦ 1000 )

輸出說明 :

請按照輸入的順序,求出對於 ( x , y ) 有多少個點 ( a , b )

在它的左下方 a < x , b < y

範例輸入 : 
5
961 404
640 145
983 888
539 71
437 532

範例輸出 :

2
1
4
0
0

提示 :

Segment tree(ST)
Binary indexed tree(BIT)

出處 :

ST | BIT | 98台中區程式題 (管理:morris1028)

以前的確是用 ST 和 BIT 去解決這個問題。

現在回過頭來思考一下如何使用 D&C 來對付這一道題。

首先,思考對於 x 軸的劃分,類似於 merge sort。

當區間合併時,排序對照 y 軸大小排序,因此合併時可以得到比它 y 值還小的個數。

但是由於要對 x 軸劃分,進行 D&C 前,先使用預排序解決。

因為會有相同 x 座標的問題,為了防止計算上的疑慮(因為合併時無法保證 x 軸的單調)

因此再對 y 軸做降排序。

#include <stdio.h>
#include <algorithm>
using namespace std;
struct Pt {
    int x, y, idx, r;
    Pt(int a=0, int b=0, int c=0):
        x(a), y(b), idx(c), r(0) {}
    bool operator<(const Pt &a) const {
        if(x != a.x)
            return x < a.x;
        return y > a.y;
    }
};
Pt D[10005], X[10005];
void DCmerge(int l, int m, int r) {
    int idx1 = l, idx2 = m+1, top = 0;
    int d = 0, i;
    while(idx1 <= m && idx2 <= r) {
        if(D[idx1].y < D[idx2].y)
            X[top++] = D[idx1++], d++;
        else
            X[top++] = D[idx2++], X[top-1].r += d;
    }
    while(idx1 <= m)    X[top++] = D[idx1++];
    while(idx2 <= r)    X[top++] = D[idx2++], X[top-1].r += d;
    for(i = 0; i < top; i++)
        D[l++] = X[i];
}
void DC(int l, int r) {
    if(l >= r)    return ;
    int m = (l+r)/2;
    DC(l, m);
    DC(m+1, r);
    DCmerge(l, m, r);
}
int main() {
    int n, i, j;
    int x, y;
    int output[10005];
    while(scanf("%d", &n) == 1) {
        for(i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            D[i] = Pt(x, y, i);
        }
        sort(D, D+n);
        DC(0, n-1);
        for(i = 0; i < n; i++)
            output[D[i].idx] = D[i].r;
        for(i = 0; i < n; i++)
            printf("%d\n", output[i]);
    }
    return 0;
}
(悄悄話) 2020-10-21 13:10:58