zoj_1101_Gamblers_枚举_hash

发布于 2019-04-24  934 次阅读


题目大意

在一堆数中求出i+j+k=ans并使ans最大

思路

现将数组降序排序,然后枚举ans,j,k,然后找i是否在数列中出现过,用hash来进行查找O(n^3)
zoj输入输出要%lld而不可以%I64d。。。

#include 
#include 
using namespace std;
#define M 1000007
long long a[M+1],h[M+1],n;
bool cam(long long x,long long y)
{
    return x>y;
}
int insert(long long x)
{
    long long y=x;
    if (y<0) y=y*-1;
    long long i=y%M;
    while (h[i]!=-2147483647&&h[i]!=x) i=i%M+1;
    h[i]=x;
}
int find(long long x)
{
    int y=x;
    if (y<0) y=y*-1;
    int i=y%M;
    while (h[i]!=-2147483647&&h[i]!=x) i=i%M+1;
    if (h[i]==x) return true;
    else return false;
}
int ll()
{
        for (int i=0;i<=M;i++)
            h[i]=-2147483647;
        for (int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            insert(a[i]);
        }
        sort(a+1,a+n+1,cam);
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                for (int k=i+1;k<=n;k++)
                    if (i!=j&&j!=k)
                    {
                        long long t=a[i]-a[j]-a[k];
                        if (t!=a[i]&&t!=a[j]&&t!=a[k])
                            if (find(t)==true)
                            {
                                printf("%lld\n",a[i]);
                                return 0;
                            }
                    }
        printf("no solution\n");
        return 0;
}
int main()
{
    scanf("%lld",&n);
    while (n!=0)
    {
        ll();
        scanf("%lld",&n);
    }
}
]]>