[ZJ][N*NlogN][BIT] a533. IOI2004 Day1.1.阿特米斯＠Morris' Blog

2012-09-23 15:38:01| 人氣915| 回應0 | 上一篇 | 下一篇

[ZJ][N*NlogN][BIT] a533. IOI2004 Day1.1.阿特米斯

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

內容：

宙斯給森林女神阿特米斯一塊矩形土地種植樹木。這塊矩形土地的左邊位於正Y軸，下邊位於正X軸，左下方位於(0,0)原點。宙斯告訴阿特米斯神樹木只能種在矩形土地內的的整數點上。阿特米斯神希望森林看起來非常自然，所以她種樹的時候會注意任何兩棵樹的連線都不會與X軸或Y軸平行。

宙斯有時候會請阿特米斯神依下列條件為他砍樹：

1. 宙斯希望至少要砍T棵樹。

2. 宙斯希望提倡足球運動，所以阿特米斯神必須將一矩形區域內的所有樹都砍倒，同時不能砍任何未於該區域外的樹。

3. 此矩形區域的每一邊都與X軸或Y軸平行。

4. 此矩型區域的一組對角必須位於樹的位置上，而且這兩棵位於對角的樹也必須砍除。

阿特米斯神非常喜歡樹，所以她希望以砍倒最少的樹來滿足上數條件。請寫一個程式，從樹木種植情形及給定之最少需砍數目棵樹T，找出此矩形區域。

輸入說明：

輸入第一行為一整數N，代表森林中的樹木棵數。第二行為一整數T，代表需砍倒的最少數目棵數。之後的N行紀錄樹的位置。第一行有兩個整數X及Y，代表樹位置的X及Y座標。X座標在Y座標之前。

輸出說明：

輸出只有一行，~~包含兩個以一空白隔開的整數~~I及J。阿特米斯神會使用第I棵(輸入的第I+2行)及第J棵樹(輸入的第J+2行)作為砍樹矩形區域的兩個對角。選取區域的最佳方法可能超過一種，但你只需輸出其中一種，I及J~~的輸出順序不重要。~~每一組測試資料都存在至少一組解。

為了judge方便，請只輸出最少要砍倒幾棵樹的數量。

範例輸入： help

範例輸入1321 12 35 6範例輸入2645 11 24 32 43 56 6

範例輸出：

範例輸出12範例輸出25

提示：

在所有的輸入中，1<N≤20000, 0≤X,Y≤64000 且1<T≤N。

除此之外，在50%的輸入中，1<N<5000。

1.由於當年比賽主機特強，看似不合理的複雜度是可以在1s內過的..

2.ZJ主機特強

3.注意記憶體限制

出處：

IOI2004 Day1 第一題 (管理：david942j)

這題的複雜度真的是看似不合理, 卻能通過, 為什麼是 N*NlogN呢, 這裡解釋一下,

我們先排序座標 x 軸依序由小到大, 接著我們使用樹狀數組(BIT), 去累計

對於某一個左端點 Pi, 使用新的一個 BIT, 分成上下兩組, 然後查詢小於等於 D[j].y 的值,

我不太會解釋, 或許你可以看程式碼理解, 當然有人願意提供比較詳細的題解也行,

幫我解釋也好 ...

#include <stdio.h>
#include <stdlib.h>
typedef struct {
    unsigned short x, y;
} Pt;
int cmp(const void *i, const void *j) {
    static Pt *a, *b;
    a = (Pt *)i, b = (Pt *)j;
    return a->x - b->x;
}
int main() {
    int n, t, i, j;
    while(scanf("%d %d", &n, &t) == 2) {
        Pt D[n];
        int L = 0;
        for(i = 0; i < n; i++) {
            scanf("%hu %hu", &D[i].x, &D[i].y);
            D[i].x++, D[i].y++;
            if(D[i].y > L) L = D[i].y;
        }
        qsort(D, n, sizeof(Pt), cmp);
        int ans = 0xfffffff;
        for(i = 0; i < n; i++) {
            short upC[64005] = {}, doC[64005];
            int uCnt = 0, dCnt = 0, idx, sum;
            for(j = i; j < n; j++) {
                if(D[j].y >= D[i].y) {
                    uCnt++;
                    idx = D[j].y;
                    while(idx <= L) {
                        upC[idx]++;
                        idx += idx&(-idx);
                    }
                    if(uCnt >= t) {
                        sum = 0, idx = D[j].y;
                        while(idx) {
                            sum += upC[idx];
                            idx -= idx&(-idx);
                        }
                        if(sum >= t && sum < ans)
                            ans = sum;
                    }
                } else {
                    dCnt++;
                    idx = D[j].y;
                    while(idx <= D[i].y) {
                        doC[idx]++;
                        idx += idx&(-idx);
                    }
                    if(dCnt >= t) {
                        sum = 0, idx = D[j].y;
                        while(idx) {
                            sum += doC[idx];
                            idx -= idx&(-idx);
                        }
                        sum = dCnt - sum;
                        if(sum >= t && sum < ans)
                            ans = sum;
                    }
                }
            }
            if(ans == t)    break;
        }
        printf("%d\n", ans);
    }
    return 0;
}

我要檢舉

#a533#IOI2004 Day1.1#阿特米斯

台長： Morris

您可能對以下文章有興趣

a094. NOI2003 Day1.1.木棒游戏

[ZJ][DP] a365. 3. 新井字遊戲

[ZJ][BIT] a484. 美麗風景遞增之路

[ZJ][模擬水] a349. 2. 指令解譯器

人氣(915) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[ZJ][數學解] a534. IOI2008 Day2.1.花園問題
此分類上一篇:[ZJ][二分+凸包計算面積] b221. 6. 耕者有其田

回應(0)