解題區/解題區 - Zerojudge

b317. 紅圓茵可的野望

contents

  1. 1. 內容 ：
  2. 2. 輸入說明 ：
  3. 3. 輸出說明 ：
  4. 4. 範例輸入 ：
  5. 5. 範例輸出 ：
  6. 6. 提示 ：
  7. 7. Solution

內容 ：

紅圓茵可最近隱居在板擦山研究魔法師的夢想，傳說中的魔法－「召喚蘿莉」。
只要成功練就這個魔法，茵可就可以召喚出一堆蘿莉，然後跟一堆蘿莉一起……嘿嘿嘿…..
目前茵可已經研究出N種可能可以成功魔法陣，接下來就是要測試這些魔法陣能不能成功召喚蘿莉，因為數量實在太多了，所以他決定先測試其中K種。為了測試魔法陣，茵可需要先開一個異次元空間，並且在裡面做測試(因為召喚蘿莉是個極大的魔法，發動時可能會造成空間扭曲，不小心毀掉可茵城就不好了。)。魔法陣都是圓形的，半徑為r，發動一個魔法陣需要以魔法陣為底高度為h的圓柱體空間。而茵可只能開出長方體的異次元空間，一個異次元空間有其長、寬、高，而魔法陣只能放置在該空間的地板上(長 x 寬那一面)，所以要發動一個半徑為r，高度為h的魔法陣，茵可需要開一個長2r寬2r高h的異次元空間(體積2r x 2r x h)。現在茵可想要開一個異次元空間，而這個空間至少要能發動K個魔法陣(不必同時發動)，這個空間的體積至少是多少。

輸入說明 ：

第一行有兩個正整數 N,K(K<=N)
接下來N行每行有兩個正整數r,h代表一個魔法陣的半徑及發動需要高度(r,h<=100)

測資

  1. N<=100
  2. N<=100
  3. N<=100
  4. N<=100000
  5. N<=100000

輸出說明 ：

輸出要發動其中K個魔法陣所需最小的異次元空間的體積是多少

範例輸入 ：

1
2
3
4
5
6
5 3
1 1
1 2
2 5
2 3
1 4

範例輸出 ：

1
16

提示 ：

範測所需體積為 224=16

可發動第1、2、5個魔法陣

Solution

這一題有兩種做法，直接窮舉 O(100 * 100) 的針對 [r, h] 找到 [0, r] x [0, h] 的數量是否大於 K，那麼可以在線性時間內完成。

而下面的做法，算是多此一步，原本想說能不能用 O(n log n) 時間內完成，但是會缺少部分調整資訊，也就是單純排序，以掃描線的基準會漏到資訊。

如果這一題的 r, h 很大的話，窮舉還是會耗費 O(n^2 log n)，套用當前最佳解剪枝應該快上很多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
int BIT[256];
int query(int x) {
    int ret = 0;
    for (; x; x -= x&(-x))
        ret += BIT[x];
    return ret;
}
void modify(int x, int L) {
    for (; x <= L; x += x&(-x))
        BIT[x]++;
}
int main() {
    int N, K, r, h, w;
    while (scanf("%d %d", &N, &K) == 2) {
        vector<pair<int, int> > D;
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &r, &h);
            assert(r <= 100 && h <= 100 && r > 0 && h > 0);
            D.push_back(make_pair(r * 2, h));
        }
        int ret = 0x3f3f3f3f;
        sort(D.begin(), D.end());
        memset(BIT, 0, sizeof(BIT));
        for (int i = 0; i < N; i++) {
            modify(D[i].second, 255);
            for (int j = D[i].second; j <= 100; j++) {
                int q = query(j);
                w = D[i].first, h = j;
                if (q >= K)
                    ret = min(ret, w*w*h);
            }
        }
        if (K == 0)	ret = 0;
        printf("%d\n", ret);
    }
    return 0;
}