首页 > 代码库 > 【贪心】取数游戏（UPCOJ3595）

【贪心】取数游戏（UPCOJ3595）

2024-11-10 08:48:01   202人阅读

　　　　　　　　　　　　　　　　　　取数游戏

　　　　　　　　　　　　　　　　　　　　　　　时间限制: 1 Sec  内存限制: 64 MB

题目描述

给出2n(n≤100)个自然数(小于等于30000)。将这2n个自然数排成一列，游戏双方A和B从中取数，只允许从两端取数。A先取，然后双方轮流取数。取完时，谁取得数字总和最大为取胜方；若双方和相等，属B胜。试问A方是否有必胜策略？

输入

共2行，第1行一个整数n；第2行有2*n个自然数。

输出

只有1行，若A有必胜策略，则输出“YES”，否则输出“NO”。

样例输入

4
7 9 3 6 4 2 5 3

样例输出

YES

分析

    个人认为该题目描述有问题，“只允许从两端取数。A先取，然后双方轮流取数”，这句话我理解的是在取的时候两端的数想取哪个取哪个，然而我看了别人的题解才发现，它的意思是第一次A取了左端的数，那么接下来他只能取左端的。

   但是有人认为"因为要求必胜策略，他可以一直选择取奇数或偶数，最后如果结果不相等就有必胜策略。如果每次只想去两端最大的那个，而不知道b如何取，不是必胜策略！"来自http://www.mamicode.com/info-detail-1454553.html

我认为在A取了两端的一个数字后是可以判断B是如何取的，只不过判断的情况多了一些。

    我在百度文库找到了一个同样的取数游戏题，它明确说明了“两个游戏者，轮流从最右或最左取一个数。”来自https://wenku.baidu.com/view/6d7cb8fb4b73f242336c5fd1.html

    各位怎么看？在评论区写下自己的看法，交流一下吧 :-D

参考代码

#include <iostream>
#include <stdio.h>

using namespace std;

int n;
int j;
int a[201];
int sum1=0,sum2=0;

int pan(){
    for(int i=0;i<2*n;i++){
        if(i%2==0){
            sum1+=a[i];
        }else{
            sum2+=a[i];
        }
    }
    return sum1-sum2;
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<2*n;i++){
        scanf("%d",&a[i]);
    }
    j=pan();
    if(j!=0){
        printf("YES\n");
    }else{
        printf("NO\n");
    }
    return 0;
}

 

 

   

 

 

 

 

【贪心】取数游戏（UPCOJ3595）






























        

            
                
                  
                
                

                    联系

                    我们