HDU YY's new problem-蒲公英云

HDU YY's new problem

遇到一个很卡时间的题目，提交AC之后也是有时能过，有时不能过，偶然过了还真是实属不易，但是本题的思路和想法还是很需要说明一下的。

如果用纯暴力的方法，依次遍历序列中的各个数字，复杂度要O（n3），必定超时，则必须进行算法优化了，考虑到这个题目的特殊性，序列中只有n个数，而且是从1到n，需要满足的是 a-b=b-c （且a、b、c顺序不能改变）这样特点的式子，即可以转化为 a+c=2*b （且a、b、c顺序不能改变），即a+b一定要是偶数，且要采用记录下标的方法，（a+c）/2 的值所对应的下标在a的下标和c的下标之间，即可以找到满足这样关系的序列。实质为简单运用了一下Hash表。

HDU YY’s new problem http://acm.hdu.edu.cn/showproblem.php?pid=3833

代码实现如下：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[10010];
int b[10010];
int main()
{
    int t,n,sum;
    int flag;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        flag=0;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            b[a[i]]=i;   //记录下标
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=i+1; j<=n; j++)
            {
                sum=a[i]+a[j];
                if(sum%2==1)
                    continue;
                else if(sum%2==0)
                {
                    if((b[sum/2] > b[a[i]])&&(b[sum/2] < b[a[j]]))    //if((b[sum/2] > i)&&(b[sum/2] < j)
                    {
                        flag=1;
                        break;
                    }
                }
            }
            if(flag)
                break;
        }
        if(flag==1)
            printf("Y\n");
        else printf("N\n");
    }
    return 0;
}