【Zeus】算法|算法系统学习-取数先取如何必定获胜（（相对或近似贪心））【Zeus】算法|算法

取数游戏有AB 两个人轮流取2n个数中的n个数，取数之和大者为胜，若相同则先取者胜。请用算法让先取数的人胜（取数时只能看到2n个数的两边的数，即每次都只能看到该头和尾）
假设这组数为：6，16，27，6，12，9，2，11，6，5。用贪心策略每次两人都取两边的数中较大的一个数
算法分析：用贪心算法的情况来看：
假设A，B两人取数，每次都只能取两边，那么6，16，27，6，12，9，2，11，6，5，先取者胜，以A先取，取数结果为：

第几次取数	1	2	3	4	5	总和
A	6	27	12	5	11	61
B	16	6	9	6	2	29

所以A胜出
但是如果数据的不同也将会影响结果
假设这组数据为：
16，27，7，12，9，2，11，6 如果仍然用贪心算法，先取数时A败

第几次取数	1	2	3	4	总和
A	16	7	9	11	43
B	27	12	6	2	47

所以B胜出
其实，我们只能看到两边的数据，无论是先取还是后取都无法保证100%胜出，因此我们这时一般的策略是用近似贪婪算法。
数学模型建立：假设A和B玩这游戏，N个数排成一行，从左到右编号，依次是1，2，3........N因为N为偶数，又因为A先取数，B后取，，所以A可以一开始选择先取奇数（即最左边的数），又可以选择偶数（即最右边的数）

假设A第一次取奇数编号（编号为1）的数，则接着B只能取到偶数编号（编号为2或者N）的数。
假设B第一次取到偶数编号（编号为N）的数，则接着B只能取到奇数编号（编号为1或N-1）的数。

因此无论A第一次怎么取数，而B只能取到另一边的数（偶编号或者奇编号）的数
以上是对第一个回合的分析，显然对后续也是一样的适用的。也就是说，A能够让B自始至终只取一种编号的数。这样，我们只要比较奇编号之和与偶编号之和，谁大，以决定最开始A是取奇数还是偶数即可。
算法设计：有了以上的数学模型，那么我们只需要计算一组数的奇数位和偶数位的数据之和，然后就可以确定先取数者必胜的取数方式。

main(){ int i,s1,s2,data; cin>>n; s1=0; s2=0; for(i=1; i<=n; i++){ cin>>data; if(i mod 2=0){ s2=s2+data; }else{ s1=s1+data; } }if(s1>s2){ cout<<"拿左边"}else{cout<<"拿右边"} } 复制代码

因此，在算法设计之前数学模型的选择是非常重要的。
【【Zeus】算法|算法系统学习-取数先取如何必定获胜（（相对或近似贪心））】