解題區/解題區 - UVa

UVa 12598 - Starting School

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Output for Sample Input
  6. 6. Solution

Problem

The first day of school is a very memorable day to everyone. Po is starting school from today and Po is very excited. As this is Po’s first day at school, no one is assigned roll number yet. So all the students form a line in the school field and they are being assigned roll number one by one. The teacher is a bit crazy. Instead of assigning roll number from 1, she starts assigning them one by one in a random fashion. Po watches this madness for the first K students and then steps up. Po says Po can assign them very easily for the rest of the students. The idea is very simple. Roll number should be unique and a student should get the smallest roll number that has not been assigned yet to any of the students. For example if K = 4, total number of students are 10 and the first K students’ roll numbers are 1, 3, 5, 10 then the next 6 roll numbers should be 2, 4, 6, 7, 8 and 9.

開學第一天是值得紀念的，Po 從今天開始在這所學校上課，他相當地興奮。Po 到達學校的第一天，沒有人被指派座號，因此所有的學生都在操場上等著被一個接著一個發送座號。老師有點喪心病狂，一開始從 1 號開始發送，但是他採用隨機發送，並沒有按著順序發。Po 看到前 K 位同學被這麼發送，Po 認為自己可以發送剩餘的學生編號，而發送方式相當簡單，將剩餘的最小座號發送給當前編號最小 (一開始規定學生編號為 1 - n) 的學生。

K = 4，一開始指派編號給 1 3 5 10 的學生座號，而剩餘座號就是發送順序為 2 4 6 7 8 9。

Though this is a very good idea, the teacher got mad at Po. So she starts asking the roll number for various students. As there are many students, Po is feeling helpless. Can you help Po?

Input

First line will contain an integer T (T <= 30), the number of test cases. Each case will start with three integers N (0 < N <= 109), K (0 < K <= 50,000 and K <= N) and Q (0 < Q <= 50,000). N is the total number of students, K is described earlier and Q is the number of queries of the crazy teacher. Next line will contain K distinct integers, the first K roll number assigned by the teacher. These values will be between 1 and 1000000000 (inclusive). Next will be Q integers, each indicating a position of students. These values will be between 1 and N (inclusive). (Large input output file, use faster I/O)

Output

For each case print one line “Case T:” where T is the case number. Then for each query print one line with the roll number of the student standing on the queried position. See sample I/O for clarity.

Sample Input

1
2
3
4
5
6
7
2
10 4 4
1 3 5 2
5 6 9 10
10 3 2
10 1 9
4 10

Output for Sample Input

1
2
3
4
5
6
7
8
Case 1:
4
6
9
10
Case 2:
2
8

Solution

題目解法：

將沒有分配到的連續區間壓縮，接著對於詢問二分搜索即可。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int A[65536], B[65536], C[65536], D[65536];
int main() {
    int testcase, cases = 0, N, K, Q;
    int x, l, r;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d %d", &N, &K, &Q);
        for(int i = 1; i <= K; i++)
            scanf("%d", &A[i]), B[i] = A[i];
        sort(B + 1, B + 1 + K);
        B[0] = 0, B[K+1] = N + 1;
        int M = 1;
        C[0] = 0;
        for(int i = 1; i <= K + 1; i++) {
            l = B[i - 1] + 1, r = B[i] - 1;
            if(l <= r) {
                C[M] = C[M - 1] + r - l + 1;
                D[M] = l;
                M++;
            }
        }
        printf("Case %d:\n", ++cases);
        while(Q--) {
            scanf("%d", &x);
            if(x <= K)
                printf("%d\n", A[x]);
            else {
                x -= K;
                int pos = lower_bound(C, C + M, x) - C;
                printf("%d\n", D[pos] + x - C[pos-1] - 1);
            }
        }
    }
    return 0;
}

加速 IO 的做法如下，優化輸入函數，以及反饋的二分搜索，但是排名還是沒有達到想要的目標。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int A[65536], B[65536], C[65536], D[65536];
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int testcase, cases = 0, N, K, Q;
    int x, l, r;
    ReadInt(&testcase);
    while(testcase--) {
        ReadInt(&N);
        ReadInt(&K);
        ReadInt(&Q);
        int *p = A + 1, *q = B + 1;
        for(int i = 1; i <= K; i++, p++, q++) {
            ReadInt(p), *q = *p;
        }
        sort(B + 1, B + 1 + K);
        B[0] = 0, B[K+1] = N + 1;
        int M = 1;
        C[0] = 0;
        p = B, q = p+1;
        for(int i = 1; i <= K + 1; i++, p = q++) {
            l = *p + 1, r = *q - 1;
            if(l <= r) {
                C[M] = C[M - 1] + r - l + 1;
                D[M] = l;
                M++;
            }
        }
        printf("Case %d:\n", ++cases);
        int prevX = 0, prevP = 0, pos;
        while(Q--) {
            ReadInt(&x);
            if(x <= K)
                printf("%d\n", A[x]);
            else {
                x -= K;
                if(x >= prevX)
                    pos = lower_bound(C + prevP, C + M, x) - C;
                else
                    pos = lower_bound(C, C + prevP, x) - C;
                printf("%d\n", D[pos] + x - C[pos-1] - 1);
                prevX = x, prevP = pos;
            }
        }
    }
    return 0;
}