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;
}
上一篇:vue修饰符学习


下一篇:Java——列表框:JList