解題區/解題區 - UVa

UVa 1383 - Harmony Forever

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

  • 加入一個數字 X 於陣列尾端
  • 找到序列中 mod Y 的最小值的數字 X 位置，如果有相同的，取最後加入的數字位置。

Sample Input

1
2
3
4
5
6
7
8
9
10
5 
B 1 
A 5 
B 10 
A 5 
A 40 
2 
B 1 
A 2
0

Sample Output

1
2
3
4
5
6
7
Case 1: 
1 
2 
1 
Case 2: 
1

Solution

怎麼想都沒有好的思路，最後還是用多次區間查找來完成這個最小值詢問。

每一次查詢區間 [0, Y - 1]、[Y, 2Y - 1]、[2Y, 3Y - 1] … 的最小值。

因此每一次會需要詢問 O(500000 / Y * log (500000))，當 Y 夠大的時候，效率會比直接搜索來得快，如果 Y 太小則直接搜索的效果會比較好，因為增加的數字 X 最多 40000 個。

閥值 5000。

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
81
82
83
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 524288
struct E {
    int value, index;
    E(int a = 0, int b = 0):
        value(a), index(b) {}
    bool operator<(const E &a) const {
        return value < a.value;
    }
};
E tree[(MAXN<<1) + 10];
int M;
void setTree(int s, int t) {
    int i;
    for(i = 2 * M - 1; i >= 0; i--) {
    	tree[i] = E(0x3f3f3f3f, 0);
    }
}
E query(int s, int t) {
    E ret(0x3f3f3f3f, 0);
    for(s = s + M - 1, t = t + M + 1; (s^t) != 1;) {
        if(~s&1)
            ret = min(ret, tree[s^1]);
        if(t&1)
            ret = min(ret, tree[t^1]);
        s >>= 1, t >>= 1;
    }
    return ret;
}
void update(int s, E v) {
    tree[s + M] = v;
    for (s = s + M; s > 0; s >>= 1)
        tree[s] = min(tree[s], v);
}
int main() {
    int n, x, cases = 0;
    char cmd[5];
    while (scanf("%d", &n) == 1 && n) {
        for (M = 1; M < 500000+2; M <<= 1);
        setTree(0, M);
        int B = 0;
        vector<int> BX;
        if (cases++)
            puts("");
        printf("Case %d:\n", cases);
        for (int i = 0; i < n; i++) {
            scanf("%s %d", cmd, &x);
            if (cmd[0] == 'B') {
                update(x + 1, E(x + 1, ++B));
                BX.push_back(x);
            } else {
                if (BX.size() == 0)
                    puts("-1");
                else if (x < 5000) {
                    int mn1 = 0x3f3f3f3f, mn2 = -1, u;
                    for (int i = BX.size() - 1; i >= 0; i--) {
                        u = BX[i]%x;
                        if (u == 0) {
                            mn1 = 0, mn2 = i + 1;
                            break;
                        }
                        if (u < mn1)
                            mn1 = u, mn2 = i + 1;
                    }
                    printf("%d\n", mn2);
                } else {
                    int mn1 = 0x3f3f3f3f, mn2 = -1;
                    for (int y = 0; y <= 500000; y += x) {
                        E t = query(y + 1, min(y + 1 + x - 1, 500000));
                        if (t.value - y < mn1 || (t.value - y == mn1 && t.index > mn2))
                            mn1 = t.value - y, mn2 = t.index;
                    }
                    printf("%d\n", mn2);
                }
            }
        }
    }
    return 0;
}