ZOJ 1101 Gamblers
2024-09-29 09:48:16
题目大意:一群人聚众赌博。每个人先分别押注不同的金额,可以相互借钱。开奖之后,如果某个人的押注的金额正好等于任何其他三个人金额总和,那这个人就赢得其他三个人的赌注。如果同时有两个以上的赢家,押注金额最大的那个人是最终的赢家。首先输入玩家的个数,然后输入每个玩家的押注金额,经过运算输出赢家的财富(或者 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;
}
最新文章
- 【皇甫】☀初识AOP
- 京东2017校园招聘笔试题 【第K个幸运数】
- maven之ubutu安装
- vc++ 加载,卸载自己的驱动程序
- ViewController之间的切换动画
- Challenge Checkio(python)—初尝python练习网站
- php设计模式之迭代器模式
- linux下如何解压和压缩文件
- 中介者模式(Mediator)
- [OC] NSTimer
- 20175324王陈峤宇 《Java程序设计》第六周学习总结
- bootstrap登录界面
- 关于hash冲突的解决
- python全栈开发day37-html
- HAProxy实现slave负载均衡[高可用]
- 『TensotFlow』RNN中文文本_下_暨研究生开学感想
- ASP.NET Core开源地址
- SQL慢查询安装过程
- 004 @PathVariable映射URL绑定的占位符
- cocos2d-x 数据存储