ZOJ 1101 Gamblers

原题链接

题目大意：一群人聚众赌博。每个人先分别押注不同的金额，可以相互借钱。开奖之后，如果某个人的押注的金额正好等于任何其他三个人金额总和，那这个人就赢得其他三个人的赌注。如果同时有两个以上的赢家，押注金额最大的那个人是最终的赢家。首先输入玩家的个数，然后输入每个玩家的押注金额，经过运算输出赢家的财富（或者 no solution)。

解法：

参考代码：参考了下面链接的文章。首先，对所有押注金额进行从小到大排序，然后用枚举法试。因为并列的赢家取押注最多的获胜，所以从后往前试赢家的押注金额。稍作分析可知三个数当中，至少要有一个数在目标数的左边（小于），另外两个数可能在左边，也可能在右边（因为押注金额可以为负）。最外层循环是目标数，第二和第三层是前两个数的枚举，在第二个数和最大值之间查找第三个数。找到了就返回结果。

/*

*	reference: www.cnblogs.com/pcoda/archive/2012/09/02/2667981.html

*

*

*/

#include<iostream>

#include<algorithm>

using namespace std;

int n,amount[1002];

int work();

int search(int k,int val);

int main(){

	int i,ans;

	while(cin>>n&&n){

		for(i=0;i<n;i++)

			cin>>amount[i];

		sort(amount,amount+n);

		ans=work();

		if(ans==-1)cout<<"no solution"<<endl;

		else cout<<amount[ans]<<endl;

	}

	return 0;

}

int work(){

	int i,j,k,tmp,pos;

	for(i=n-1;i>0;i--){    //赢家的押注金额

		for(j=0;j<i;j++){    //第一个押注金额

			for(k=j+1;k<n;k++){    //第二个押注金额

				tmp=amount[i]-amount[j]-amount[k];

				pos=search(k,tmp);    //在第二个数和最大值之间查找第三个数

				if(pos&&pos!=i) return i;

			}

		}

	}

	return -1;

}

int search(int k,int val){    //二分法查找

	int l,m,r;

	l=k+1;

	r=n-1;

	while(l<=r){

		m=(l+r)>>1;

		if(amount[m]==val) return m;

		if(amount[m]<val) l=m+1;

		else r=r-1;

	}

	return 0;

}