GitBook

这里写图片描述 这里写图片描述

因为题目数据范围很小 所以用标记法比较好理解

用二分查找的话 就是先把空间时间都统计出来 然后用二分查找来找到 大于q并且最接近q的空闲时间

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[200200],b[200200];
int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		int n,m;
		scanf("%d %d",&n,&m);
		for(int i=1; i<=n; i++) {
			int t;
			scanf("%d",&t);
			a[t]=1;
		}
		int cnt=0;
		for(int i=0; i<200020; i++)
			if(!a[i])
				b[cnt++]=i;
		while(m--) {
			int t;
			scanf("%d",&t);
			if(!a[t]) {
				printf("%d\n",t);
				continue;
			}
			int l=0,r=cnt;
			while(l<=r) {
				int mid=(l+r)/2;
				if(b[mid]>=t)
					r=mid-1;
				else
					l=mid+1;
			}
			printf("%d\n",b[l]);
		}
	}
	return 0;
}

题目地址:【杭电】[4907]Task schedule