Task schedule

1
5 5
1 2 3 5 6
1
2
3
4
5

4
4
4
4
7

一开始想的是如果当前时间没有被占用，时间输出当前时间，如果被占用，就向后查找，知道找到空闲时间为止，但这是超时的.....每次询问都要向后查找，而且询问的次数又那么多，肯定不行。后来打表预处理一下，把每个时间的任务的空闲时间预先处理，这样查询的时候就O(1）了。

代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn=1e5+5;
bool hash[maxn*2];
int f[maxn*2];
int T,n,m,ti,q;

void prepare()
{
    int cur=maxn*2;//始终是空闲时间
    for(int i=maxn*2;i>=1;i--)
    {
        if(hash[i]==0)
            cur=i;
        f[i]=cur;
    }
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        memset(hash,0,sizeof(hash));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&ti);
            hash[ti]=1;
        }
        prepare();
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&q);
            printf("%d\n",f[q]);
        }
    }
    return 0;
}

[BestCoder Round #3] hdu 4907 Task schedule (模拟简单题）,布布扣,bubuko.com

[BestCoder Round #3] hdu 4907 Task schedule (模拟简单题）

原文：http://blog.csdn.net/sr_19930829/article/details/38369603