[ZJ][D&C] d847 2D rank finding problem＠Morris' Blog

2013-11-09 19:57:28| 人氣29,996| 回應1 | 上一篇 | 下一篇

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

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

二度空間上的排名計算問題(2D rank finding problem)：給定二度平面空間(2D)上的點A = (a₁,a₂)與點B = (b₁,b₂)，其大小關係定義為若A > B 若且唯若 a₁> b₁ 且 a₂ > b₂ ;亦即A點在B點的右上方。如下圖中，B >A, C>A, D>A, D>C, D> B。值得注意的是，並非任意兩點均可以決定大小關係，如下圖中的點A與點E，點D與點E等，無法決定這兩點的大小關係故為無法比較(incomparable)。給定N個點(x₁,y₁), (x₂,y₂), …, (x_n,y_n)，定義某一個點的排名(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

範例輸入：

範例輸出：

提示：

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;
}

我要檢舉

#d847#2D rank finding problem

台長： Morris

您可能對以下文章有興趣

d827. 買鉛筆

[ZJ] a746 画蛇添足、a799 正值國、a753 一、最大面積

[ZJ][單調堆] b123 最大矩形 (Area)

[ZJ][dp] b123 最大矩形 (Area)

人氣(29,996) | 回應(1)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][單調堆] b123 最大矩形 (Area)
此分類上一篇:[ZJ][遞迴] a268 河內塔問題

回應(1)