解題區/解題區 - Zerojudge

b315. 紅圓茵可的考驗

contents

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

內容 ：

身為魔法師的你，想讓自己變得更強大，於是前來膜拜紅圓茵可，同時想請教他學習魔法的秘訣。經過日復一日的嘗試，你終於通過了柏油路，並且來到茵可家。「看在你這麼努力的份上，我就稍微指導你一下吧。」茵可說道。「所謂魔法，跟程式設計很像，就是一堆指令的結合。將分子移動、放熱、發光等等基礎的小魔法結合在一起，就會變成強大的魔法(像是防護罩就是控制空氣分子的移動，並使其重新排列成為堅固的結構，達到防禦的效果。)。所以說，腦中運算的能力是很重要的。」語畢，茵可大大丟給你一個題目:

給你N個數字，挑出其中兩個數字可以得到一個數字差(非負)，而N個數字會有N*(N-1)/2個數字差，問第K大數字差是多少?
如範例輸入，數字差有6個，分別為9(10-1)、7(8-1)、5(10-5)、4(5-1)、3(8-5)、2(10-8)，其中第5大的是3。

「等你能在1秒內解完這個問題再來找我吧!」隨後茵可打開比較大的門走掉了。

輸入說明 ：

第一行有兩個正整數N,K
接下來有N個整數(0<=每個整數<=1,000,000,000)

測資

  1. N<=10，K<=N*(N-1)/2
  2. N<=1,000，K<=N*(N-1)/2
  3. N<=10,000，K<=10,000
  4. N<=100,000，K<=100,000
  5. N<=100,000，K<=1,000,000,000

輸出說明 ：

輸出第K大數字差

範例輸入 ：

1
2
4 5
1 5 8 10

範例輸出 ：

1
3

Solution

使用二分搜索答案，通常是查找第 K 小的元素，這題是換成第 K 大元素，那麼就反過來找，中間調校的時候要特別小心。

代碼效率是 O(n log^2 n)，事實上可以壓成 O(n 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <stdio.h>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
int kThDiff(int A[], int n, long long m) {
    int mx = A[0], mn = A[0];
    for (int i = 0; i < n; i++)
        mx = max(mx, A[i]), mn = min(mn, A[i]);
    int l = 0, r = mx - mn, mid, ret;
    m = (long long) n * (n-1)/2 - m + 1;
    long long cnt;
    sort(A, A+n);
    while (l <= r) {
        mid = (l + r)/2;
        cnt = 0;
        for (int i = 0; i < n; i++) {
            int pos = (int)(upper_bound(A+i, A+n, A[i] + mid) - A);
            cnt += pos - i - 1;
        }
        if (cnt >= m)
            r = mid - 1, ret = mid;
        else
            l = mid + 1;
    } 
    return ret;
}
int main() {
    int n, m, A[131072];
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        printf("%d\n", kThDiff(A, n, m));
    }
    return 0;
}
/*
9 4
4 6 3 7 7 5 0 8 9 
5 1
7 4 2 5 2 
10 3
4 6 9 8 7 1 1 4 2 0 
9 20
3 8 6 2 1 9 6 7 2 
2 1
2 6 
4 4
0 9 0 0 
5 7
4 0 9 1 8 
11 30
1 2 1 6 1 0 7 7 5 2 5 
4 3
4 7 5 8 
2 1
1 6 
10 40
7 5 5 0 2 9 4 9 6 2 
3 2
6 8 7 
10 28
3 5 0 8 1 1 7 9 2 1 
9 3
6 7 1 2 0 8 5 1 0 
8 22
0 3 1 9 1 8 4 7 
11 20
2 3 0 4 7 1 7 6 2 2 1 
3 1
7 3 9 
4 2
9 2 4 5 
10 39
6 5 2 3 6 1 1 8 1 9 
8 7
4 9 7 2 1 6 3 2 
*/