首页 > 代码库 > hdoj 4907 Task schedule 【预处理】

hdoj 4907 Task schedule 【预处理】

题意:中文题,你懂得。。。

思路:建两个数组,一个标记,一个放答案(就是最快能处理的任务点), 在输入数据的时候标记改位置已经有任务了,并且找出来一个最大的数max。然后从max+1,出发从大到小,依次用temp定义没有任务的序号,如果是没有被标记那么就将该处的答案定义为temp。

题目链接 点击打开链接

代码:

#include<stdio.h>
#include<string.h>
#define MAXN 200005
int vis[MAXN], ans[MAXN];
int main()
{
	int t, n, m, i, j, q;
	scanf("%d", &t);
	while(t --){
		int a;
		memset(vis, 0, sizeof(vis));
		memset(ans, 0, sizeof(ans));
		int k = 0;
		int max = 0;
		scanf("%d%d", &n, &m);
		for(i = 1; i <= n; i ++){
			scanf("%d", &a);
			vis[a] = 1;
			if(max < a)
			max = a;
		}
		int temp = max+1;
		for(i = max; i > 0; i --){
			if(vis[i])
			 ans[i] = temp;
			 else
			 temp = i;
		}
		while(m --){
			scanf("%d", &q);
			if(!vis[q]){
				printf("%d\n", q);
			}
			else
			printf("%d\n", ans[q]);
		}
	}
	return 0;
}