1. HDU 4907：http://acm.hdu.edu.cn/showproblem.php?pid=4907
中文题我就不说题意了，直接说解题思路吧！
① 第一种思路就是我比赛时的思路，将a数组先全部清为零，当输入机器在ti时间执行第i个任务时，将a[ti]置为1，开始输入q（表示在q时间有一个工作表之外的任务请求）写一个循环，让a数组从a[q]开始循环，直到找到a[J]为0，输出j。这种方法时间超限了，但是在输入q之前先预处理，打一个表就不会超时了。
附上代码：
#include<stdio.h>
#include<string.h>
int t[],s[];
int main()
{
int T,m,n,i,j,k,a;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&m,&n);
memset(t,,sizeof(t));
for(i=; i<=m; i++)
{
scanf("%d",&a);
t[a]=;
}
memset(s,,sizeof(s));
k=;
for(i=; i<=; i++)
if(t[i]==)
{
for(j=k; j<=i; j++)
s[j]=i;
k=i+;
}
while(n--)
{
scanf("%d",&a);
printf("%d\n",s[a]);
}
}
return ;
}
②第二种思路是二分法，输入a[],后排下序，然后记录每个数字出现的位置，对于询问q,如果q不存在直接输出q，
如果q存在，假设q所在的位置为pos，那么二分【pos,n】,二分判断的依据是如果mid-p==a[mid]-a[p],那么left=mid+1,否则right=mid-1.
附上代码：
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
#define maxn 100010
int a[maxn];
int main()
{
int T,i;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
for(i=; i<n; i++)
scanf("%d",&a[i]);
sort(a,a+n);
while(m--)
{
int q;
scanf("%d",&q);
int pos=int(lower_bound(a,a+n,q)-a);
if(pos==n||a[pos]!=q)
printf("%d\n",q);
else
{
int left=pos+,right=n;
while(left<right)
{
int mid=(left+right)>>;
if(a[mid]-q==mid-pos)
left=mid+;
else
right=mid;
}
printf("%d\n",a[left-]+);
}
}
}
return ;
}
后记：
函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置。