题解 P1732

· · 题解

看数据范围！

看数据范围！

看数据范围！

重要的事情说三遍

0<= ai<=65 536

这意味着，我们只需开一个bool数组储存对应数字是否已经出现过，然后从当前数字开始向左、向右遍历（注意要遍历自己）就可以找到最近已经出现过的的数字aj。最后num[now]=true即可。

所以，这题普及-，代码很短，那就直接上代码吧。

#include<cstdio>
#include<cstring>
bool hav[65537];
int main()
{
    int n,t,i,ans,tmp;
    scanf("%d",&t);
    while(t--){
        memset(hav,false,sizeof(hav));
        scanf("%d%d",&n,&tmp);
        hav[tmp]=true;
        ans=tmp;
        while(--n){
            scanf("%d",&tmp);
            for(i=0;;i++){
                if(tmp-i>=0)
                    if(hav[tmp-i]){
                        ans+=i;
                        break;
                    }
                if(tmp+i<=65536)
                    if(hav[tmp+i]){
                        ans+=i;
                        break;
                    }
            }
            hav[tmp]=true;
        }
        printf("%d\n",ans);
    }
    return 0;
}