Gamblers

原题:Zoj 1101

题目大意

游戏开始时，他们各自将自己的赌注盖住,同时任何两个赌徒的赌注是不同的,如果其中一个赌徒没有钱了,他可以借一些筹码,但是他的赌注就是负数了.假设,他们的赌注都是整数.然后他们揭开所有的赌注.赢家为：他的赌注是其他三个人的赌注的综合.如果赢家不止一家,那么拥有最大赌注的人是赢家.

算法分析

对于此题，求三个数n1,n2,n3使其之和为另一个数字n.如果存在多种情况,求n值最大的一个.所以首先将所有的数字从小到大排列,从后向前求解,这样就保证求得的第一个赢家为最大值.剩下的三个数枚举求得.

程序代码

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int winner;
int bet[1000];
int binsearch(int k,int val)
{
    int left,right,mid;
    left=k+1;
    right=n-1;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(bet[mid]==val) return mid;
        if(bet[mid]<val) left=mid+1;
        else right=mid-1;
    }
    return 0;
}
bool solve()
{
    sort(bet,bet+n);
    for(int i=n-1;i>=0;i--)
        for(int j=0;j<i;j++)
            for(int k=j+1;k<n;k++)
            {
                int minus,pos;
                minus=bet[i]-bet[j]-bet[k];
                pos=binsearch(k,minus);
                if(pos!=i&&pos)
                {
                    winner=i;
                    return true;
                }
            }
    return false;
}
int main()
{
    while(scanf("%d",&n)&&n)
    {
        for(int i=0;i<n;i++)
            scanf("%d",&bet[i]);
        if(solve()) printf("%d\n",bet[winner]);
        else printf("no solution");
    }
    return 0;
}