uva 12598 Starting School

本文从WordPress迁移而来, 查看全部WordPress迁移文章

二分

题意:有n个人排成一列,给出前k个人的数字,从第k+1个人开始,给他们分配数字,分配的方法是取当前没有出现过的最小正整数,例如8人,前3人的数字为3 5 8,第4到第8个人的数字分别为1 2 4 6 7,整个序列为3 5 8 1 2 4 6 7

数据很大,不可能模拟

  1. 留意到一点,因为是取最小的没用过的正整数,所以我们可以先把所有可能用的正整数保存下来,按区间保存
  2. 例如已经用了3 5 8,没用的就是
1
2
3
[1,2] 2个
[4,4] 1个
[6,8] 3个

现在

要为第k+1个人分配数字,那么可以立刻知道是分配1,因为1是第1个没有用过的

要为第k+5个人分配数字,可以立刻知道是7,因为7是第5个没有用过的数字

所以要为第m个数字分配数字,在上面没有用过的数字表里面找,先找到它在哪一块,再找到是哪一块的第几个,其中找在哪一块,用二分即可

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXK 50010
#define MAXQ 50010
#define INF 1000000010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int N,K,Q,knum[MAXK];
int usednum[MAXK];
struct segment{
int l,r,len;
segment(){}
segment(int _l,int _r,int _len){
l = _l; r = _r; len = _len;
}
};
segment s[MAXK];
int ns,sum[MAXK];

int binary(int key){
int low = 0 , high = ns-1 , ans;
while(low <= high){
int mid = (low + high) >> 1;
if(sum[mid] >= key){
ans = mid; high = mid - 1;
}
else low = mid + 1;
}
return ans;
}

int main(){
int T;
scanf("%d",&T);
for(int cas = 1; cas <= T; cas++){
scanf("%d%d%d",&N,&K,&Q);
for(int i = 1; i <= K; i++){
scanf("%d",&knum[i]);
usednum[i] = knum[i];
}
usednum[0] = 0; usednum[K+1] = INF;
sort(usednum,usednum+K+2);

ns = 0; s[0] = segment(0,0,0);
for(int i = 0; i <= K; i++){
int l = usednum[i]+1;
int r = usednum[i+1]-1;
if(r > N || i == K) r = N;
if(r < l) continue;
s[ns++] = segment(l,r,r-l+1);
if(r == N) break;
}

cl(sum,0);
sum[0] = s[0].len;
for(int i = 1; i < ns; i++)
sum[i] = sum[i-1] + s[i].len;

printf("Case %d:\n",cas);
for(int i = 0; i < Q; i++){
int pos;
scanf("%d",&pos);
if(pos <= K){
printf("%d\n",knum[pos]);
continue;
}
int num = pos - K;
int index = binary(num);
int delta = sum[index] - num;
int res = s[index].r - delta;
printf("%d\n",res);
}
}
return 0;
}