HDU YY's new problem

谁践踏了优雅 2022-08-21 03:09 11阅读 0赞

遇到一个很卡时间的题目，提交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][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;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_3833]: http://http://acm.hdu.edu.cn/showproblem.php?pid=3833