poj 2287 Tian Ji -- The Horse Racing
题意:
田忌赛马
假设3匹马变成1000匹。齐王仍然让他的马按从优到劣的顺序出赛,田忌能够按随意顺序选择他的赛马出赛。赢一局,田忌能够得到200两银子,输一局,田忌就要输掉200两银子,平局的话不输不赢。
请问田忌最多能赢多少银子?
思路:
贪心。
假设当前最好的马能够胜齐王最好的马。那么让这两匹马比一场;
假设当前最差的马能胜齐王最差的马,那么让这两匹马比一场;
假设上面两个条件都不满足。那么让当前最差的马和齐王最好的马比一场。
/*poj 2287 题意: 田忌赛马 假设3匹马变成1000匹,齐王仍然让他的马按从优到劣的顺序出赛。田忌能够按随意顺序选择他的赛马出赛。赢一局,田忌能够得到200两银子,输一局。田忌就要输掉200两银子。平局的话不输不赢。 请问田忌最多能赢多少银子?
思路: 贪心。 假设当前最好的马能够胜齐王最好的马。那么让这两匹马比一场。 假设当前最差的马能胜齐王最差的马。那么让这两匹马比一场; 假设上面两个条件都不满足。那么让当前最差的马和齐王最好的马比一场。
*/ #include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int N=1005; int a[N],b[N]; void gao(int n){ int p1=0,p2=0; int q1=n-1,q2=n-1; int ans=0; while(p1<=q1){ if(a[p1]>b[p2]){ ++p1; ++p2; ++ans; } else if(a[q1]>b[q2]){ --q1; --q2; ++ans; } else{ if(a[p1]!=b[q2]) --ans; ++p1; --q2; } } printf("%d\n",ans*200); } int main(){ int n; while(scanf("%d",&n) && n){ for(int i=0;i<n;++i) scanf("%d",&a[i]); for(int i=0;i<n;++i) scanf("%d",&b[i]); sort(a,a+n); sort(b,b+n); gao(n); } return 0; }
相关文章
- 2019/12/5BJFirstDay--scrum后台+cpp项目前台环境跑起来!!!
- HDU 3861--The King’s Problem【scc缩点构图 && 二分匹配求最小路径覆盖】
- Android--使用LayoutInflater加载布局文件的三种方法
- The "Go" Learning Trip -- 3. Go Basics2 -- Part1-3
- stat -- 获取比 ls 更多的信息
- 排序算法--计数排序(CountSort)的原理、排序过程、注意点及代码示例
- HDU 1052 Tian Ji -- The Horse Racing (贪心)
- ES6语法中--let和const 的区别
- 商品分享--图片分享
- 线性代数学习笔记(1)--二维向量点积本质(仅供自己理解)
- wp api jwt 403 (Forbidden) -- JWT is not configurated properly, please contact the admin
- stm32工程和算法分享(8)--按键切换灯的频率
- 编程之美初赛第一场--树
- Inversion of Control Containers and the Dependency Injection pattern--Martin Fowler
- WebLogic Server的单点登陆功能--转载
- Pitfalls of the Hibernate Second-Level / Query Caches--reference
- Topology: The Architecture of Distributed Systems--reference
- The best career advice I’ve received --转载
- Mysql 1290 - The MySQL server is running with the --secure-file-priv option
- JavaScript高级程序设计学习笔记--变量、作用域和内存问题