首页 > 代码库 > HDU 4334 Trouble

HDU 4334 Trouble

合并排序再枚举哭


题意问五个数组中各抽一个加起来 和是否为 0。


開始想用 200*200*200 和 200*200 比。果然TLE了。

后来知道 得 200*200,200*200 ,200 。


先200*200 的枚举,排序,去重。然后三个元素加起来,微调 两个 200*200 的指针。


这题用 %lld 就WA。得用 %I64d 。贡献N多TLE。N多WA。怒刷存在感。


#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
using namespace std;
LL num[5][201];

LL sum1[201*201];
LL sum2[201*201];

int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("2","w",stdout);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=0; i<5; i++)
            for(int j=0; j<n; j++)
                scanf("%I64d",&num[i][j]);

        int len1=0,len2=0;
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                sum1[len1++]=num[0][i]+num[1][j];

        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                sum2[len2++]=num[2][i]+num[3][j];

        sort(sum1,sum1+len1);
        sort(sum2,sum2+len2);
        sort(num[4],num[4]+n);

        int l1=unique(sum1,sum1+len1)-sum1;
        int l2=unique(sum2,sum2+len2)-sum2;

        bool flag=0;
        int j,k;
        for(int i=0; i<n&& !flag; i++)
        {
            for(j=0,k=l2-1; j<l1&&k>=0;)
            {
                if(sum1[j]+sum2[k]+num[4][i]==0)
                {
                    flag=1;
                    break;
                }
                else if(sum1[j]+sum2[k]+num[4][i]>0)
                    k--;
                else
                    j++;
            }

        }

        if(flag)
            puts("Yes");
        else
            puts("No");
    }
}