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;
}