首页 > 试题广场 >

纸牌游戏

[编程题]纸牌游戏
  • 热度指数：16592 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

牛牛和羊羊正在玩一个纸牌游戏。这个游戏一共有n张纸牌, 第i张纸牌上写着数字ai。
牛牛和羊羊轮流抽牌, 牛牛先抽, 每次抽牌他们可以从纸牌堆中任意选择一张抽出, 直到纸牌被抽完。
他们的得分等于他们抽到的纸牌数字总和。
现在假设牛牛和羊羊都采用最优策略, 请你计算出游戏结束后牛牛得分减去羊羊得分等于多少。


输入描述:
输入包括两行。
第一行包括一个正整数n(1 <= n <= 105),表示纸牌的数量。
第二行包括n个正整数ai(1 <= ai <= 109),表示每张纸牌上的数字。


输出描述:
输出一个整数, 表示游戏结束后牛牛得分减去羊羊得分等于多少。
示例1

输入

3
2 7 4

输出

5
算法知识视频讲解
添加回答
进步不断头像 进步不断
Python 解法
n,m=input(),list(map(int,input().split()))
m.sort(reverse=True)
print(sum([v fori,v inenumerate(m) ifi%2==0])-sum([v fori,v inenumerate(m) ifi%2!=0]))
发表于 2018-07-18 23:03:18 回复(0)
亲爱的暴躁的热心网友皮皮文头像 亲爱的暴躁的热心网友皮皮文 
根据题目要求，牛牛妞妞抽取的牌其实不是随机的都是最优的就是从大到小抽牌，所以对牌进行排序一次抽取做差值


	# coding=utf-8





	while 1:





	    num=int(raw_input())





	    l=sorted(map(int,raw_input().split()))





	    tar=num%2





	    sumA=0





	    sumB=0





	    fori inrange(num):





	        ifi%2==tar:





	            sumA+=l[i]





	        elifi%2!=tar:





	            sumB+=l[i]





	    printabs(sumA-sumB)





	    break

发表于 2018-07-01 16:50:41 回复(0)
千言万语总是你头像 千言万语总是你
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    int *a = new int[n+1];
    int i = 0;
    for (i = 0; i<n; i++)
    {
        scanf("%d", a+i);
    }
    sort(a, a+i);
    int res = 0;
    int sign = 1;
    for (int j = n-1; j>=0; --j)
    {
        if(sign)
        {
            res += a[j];
            sign = 0;
        }
        else
        {
            res -= a[j];
            sign = 1;
        }  
    }
    printf("%d\n", res);
    return 0;
}
发表于 2018-09-02 11:20:39 回复(0)
牛客177892663号头像 牛客177892663号
import java.util.*;
 
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            Integer num[] = new Integer[n];
            for(inti = 0; i < n; i++){
                num[i] = sc.nextInt();
            }
            Arrays.sort(num, Collections.reverseOrder());
            int ans = 0;
            int flag = 1;
            for(int i = 0; i < n; i++){
                ans += num[i] * flag;
                flag = -flag;
            }
            System.out.println(ans);
        }
    }
}
编辑于 2021-04-17 15:30:57 回复(0)
zjl233头像 zjl233
Python3 type hint 
from typing import List


def score_diff(nums: List[int]) -> int:
    nums.sort(reverse=True)
    # 如果数组长度为奇数，末尾补一个0
    if len(nums) % 2 != 0:
        nums.append(0)

    diff = 0
    for i in range(0, len(nums), 2):
        diff += nums[i] - nums[i + 1]

    return diff


def oj_main():
    # 数字输入 start
    _ = int(input())
    ints = [int(s) for s in input().split()]

    int_res = score_diff(ints)
    print(int_res)
    # 数字输入 end


if __name__ == '__main__':
    oj_main()

附上牛客网 输入/输出 模板，建议搭配 PyCharm live template 食用 

from typing import List

def solution(a):
    # 这里写题解
    ...


def oj_main():
    # 数字输入 start ===========================
    n = int(input())  # 一共有 n 个输入，或 n 行输入

    ints = [int(s) for s in input().split()]  # 单行输入，用不到 n
    ints = [int(input()) for _ in range(n)]  # 多行输入
    # 上面两行只留一行

    ints_res: List[int] = solution(ints)
    print(' '.join([str(i) for i in ints_res]))  # 单行输出数字数组
    # 数字输入 end  ============================

    # 字符输入 start ---------------------------
    n = int(input())  # # 一共有 n 个输入，或 n 行输入

    words = input().split()  # 单行输入，用不到 n
    words = [input() for _ in range(n)]  # 多行输入
    # 上面两行只留一行

    words_res: List[str] = solution(words)
    print(' '.join(words_res))  # 单行输出字符数组
    # 字符输入 end ----------------------------


if __name__ == '__main__':
    oj_main()




发表于 2020-06-20 18:11:24 回复(0)
C/C++
从心开始201807031910153头像 从心开始201807031910153
#include<iostream>
#include<vector>
#include<algorithm>
usingnamespacestd;
intmain()
{
    int n, temp;
    longlongsum = 0;//n为个数，m是翻转长度
    vector<int> array;
    cin >> n;
    while(n--)
    {
        cin >> temp;
        array.push_back(temp);
    }
    sort(array.begin(), array.end());
    if(array.size() % 2 == 1)
        sum = array[0];
    for(inti = array.size() - 1; i>0; i -= 2;)
    {
        temp = array[i] - array[i - 1];
        sum = sum + temp;
    }
    cout << sum;
    return0;
}
发表于 2019-04-04 22:00:11 回复(0)
C/C++
还哈头像 还哈
一、C语言
时间不够，通过90%测试用例。
对数组a[n]进行排序，随后羊羊按照奇数数组元素相加，牛牛按照偶数数组元素相加。
#include <stdio.h>
int main()
{
    long int n;
    scanf("%ld", &n);
    long int a[100000], b[100000];
    for (long int i = 0; i<n; i++)
    {
        scanf("%ld", &a[i]);
    }
    long int middle, i = 1;
    for (; i<n; i++)
    {
        for (long int j = 0; j<i; j++)
        {
            if (a[j] <= a[i])
            {
                middle = a[i];
                for (long int f = i; f>j; f--)
                {
                    a[f] = a[f - 1];
                }
                a[j] = middle;
                break;
            }
        }
    }
    long int niuniu = 0, yangyang = 0, cha;
    for (long int i = 0; i<(n / 2 + n % 2); i++)
    {
        niuniu = niuniu + a[2 * i];
        yangyang = yangyang + a[2 * i + 1];
    }
    cha = niuniu - yangyang;
    printf("%ld", cha);
}



二、C语言
时间不够，通过60%测试用例。
对数组a[n]进行排序，随后羊羊按照奇数数组元素相加，牛牛按照偶数数组元素相加。

#include <stdio.h>

int main()
{
    long int n;
    scanf("%ld", &n);
    long int a[100000], b[100000];
    for (long int i = 0; i<n; i++)
    {
        scanf("%ld", &a[i]);
    }
    long int lastmax, max = a[0], x = 1, y = 1;
    for (long int j = 0; j<n;)
    {
        for (long int i = 0; i<n; i++)
        {
            if (y == 1)
            {
                if (max<a[i])
                    max = a[i];
            }
            if (y == 0)
            {
                if (a[i]<lastmax)
                {
                    if (x == 1)
                    {
                        max = a[i];
                        x = 0;
                    }
                    if (max<a[i])
                        max = a[i];
                   }
            }
        }
        y = 0;
        for (long int i = 0; i<n; i++)
        {
            if (max == a[i])
            {
                b[j] = a[i];
                j++;
            }
        }
        lastmax = max;
        x = 1;
    }
    long int niuniu = 0, yangyang = 0, cha;
    for (long int i = 0; i<(n / 2 + n % 2); i++)
    {
        niuniu = niuniu + b[2 * i];
        yangyang = yangyang + b[2 * i + 1];
    }
    cha = niuniu - yangyang;
    printf("%ld", cha);
}


三、C语言
时间不够，通过70%测试用例。
有n次循环，每次循环求出最大值，并把每次的最大值分给羊羊或牛牛。每次的最大值分配完，便将对应的数组元素赋值为0，使之不影响下一次最大值的求解。

#include <stdio.h>

int main()
{
    long int n;
    long int niuniu = 0, yangyang = 0, cha;
    scanf("%ld", &n);
    long int a[100000], b[100000];
    for (long int i = 0; i<n; i++)
    {
        scanf("%ld", &a[i]);
    }
    long int max = 0, i = 0, j, c;
    for (; i<n; i++)
    {
        for (j = 0; j<n; j++)
        {
            if (max<a[j])
            {
                max = a[j];
                c = j;
            }
        }
        if (i % 2 == 0)
        {
            niuniu = niuniu + max;
        }
        if (i % 2 == 1)
        {
            yangyang = yangyang + max;
        }
        a[c] = 0;
        max = 0;
    }
    cha = niuniu - yangyang;
    printf("%ld", cha);
}


发表于 2020-10-05 03:56:51 回复(0)
C/C++
CleMints头像 CleMints
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n,temp;
    vector<int> vec;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>temp;
        vec.push_back(temp);
    }
    sort(vec.rbegin(),vec.rend()); //反向迭代器进行逆向排序（从大到小）
    int res=0;
    int flag=1;
    for(int i=0;i<n;i++){
        res+=vec[i]*flag;
        flag=-flag;
    }
    cout<<res;
    return 0;
}
发表于 2020-08-10 11:33:04 回复(0)
zzmim头像 zzmim 
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
 
int main(){
    vector<long long> arr;
    long long n, m;
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>m;
        arr.push_back(m);
    }
    sort(arr.begin(), arr.end(), greater<long long>());
    long long ret = 0;
    for(int i = 0; i < n; i++){
        //cout<<arr[i]<<" ";
        if(i % 2)
            ret -= arr[i];
        else
            ret += arr[i];
    }
    cout<<ret;
    return 0;
}

发表于 2019-12-02 23:38:51 回复(0)
Python
0b100001101000头像 0b100001101000
排序，step输出 
n = input()
m = sorted(list(map(int, input().split())))
a = sum(m)
n = sum(m[::-2])
print(2*n-a)


发表于 2019-09-24 22:37:45 回复(0)
C/C++
胖十斤换网名的阿琛头像 胖十斤换网名的阿琛 
#include <iostream>
 #include <vector>
 #include <set>
 using namespace std;
 multiset<int>::reverse_iterator e;
 int main()
 {
    int n,nn,yy;
    multiset<int> s;
    while (cin >> n)
    {
        nn = yy = 0;
        for (int i = 0; i < n; i++)
        {
            int tmp; cin >> tmp;
            s.insert(tmp);
        }
        int i = 1;
        for (e = s.rbegin(); e != s.rend(); e++,++i)
            (i % 2 == 1) ? nn += *e : yy += *e;
        cout << nn - yy << endl;
        s.clear();
    }
    return 0;
 }
发表于 2019-07-06 17:11:30 回复(0)
盲夏半开头像 盲夏半开
使用快速排序，要不时间限制
发表于 2019-03-17 14:59:31 回复(1)
山人骑士头像 山人骑士
1.最优策略。所谓最优就是当轮到自己抽牌时，直接选择最大的牌。这样每当两个人都抽完了牌之后，用牛牛的牌面值减去羊羊的牌面值，就是差值的一部分。然后这样一直计算到第一个数。最后将所有的差值都加起来就得到了解。
2.还要考虑一个牌的数量的奇偶问题。如果牌数量为偶数，则将n/2个差值加起来；若牌数量为奇数，那么牌面值最小的牌直接给了牛牛，这个值要加到差值的总和里。
发表于 2018-09-14 23:06:38 回复(0)
QING0304头像 QING0304 
n = int(input())
m = list(map(int, input().split()))

score_Cow = 0
score_Goat = 0

m = sorted(m, reverse=True)

for i in range(1, n+1):

    if i % 2 == 0:
        score_Goat += m[i-1]
    else:
        score_Cow += m[i-1]

print(score_Cow - score_Goat)

发表于 2018-08-21 11:29:02 回复(0)
管子_no1头像 管子_no1
  • python3
    n = int(input())
num_list = list(map(int, input().split()))
num_list.sort(reverse=True)
s = 0
for i in range(n):
  s += (-1)**i * num_list[i]
print(s)
发表于 2019-08-16 11:55:12 回复(0)
S_Leo头像 S_Leo
python 3.x 版本：

运用数列操作：
list[start:stop:step]、
双数index是牛牛，单数index是羊羊

代码：
n,m=input(), list(map(int,input().split()))  接受输入值

m.sort(reverse = True)  排序满足最优解

print(sum(m[0::2])- sum(m[1::2]))  打印 （牛牛总和 - 羊羊总和）
发表于 2021-04-02 17:07:48 回复(0)
何之洲是网名不是真名头像 何之洲是网名不是真名
c++，降序后轮流抽牌计数 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, i;
    long ai;
    cin >> n;
    vector<long> vec(n);
    for (i = 0; i < n; i++) {
        cin >> ai;
        vec[i] = ai;
    }
    sort(vec.begin(), vec.end(), greater<long>());
    long ret = 0;
    for (i = 0; i < n; i++) {
        if (i & 0x1) {
            ret -= vec[i];
        } else {
            ret += vec[i];
        }
    }
    cout << ret << endl;
    return 0;
}


发表于 2020-08-28 10:43:24 回复(0)
阿珂酱头像 阿珂酱
if __name__ == "__main__":
    a=int(input())
    b=list(map(int,input().split()))
    b.sort(reverse=True)
    print(sum(b[0::2])-sum(b[1::2]))
发表于 2020-08-23 19:31:18 回复(0)
ICOLFORREAL头像 ICOLFORREAL 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	int n;
   cin >> n;
   vector<int>card(n, 0);
   for (int i = 0; i < n; i++)
   {
	   cin >> card[i];
   }
   sort(card.rbegin(), card.rend());
   int res = 0;
   for (int i = 0; i < n; i++)
   {
	   if (i%2==0)
	   {
		   res += card[i];
	   }
	   else
	   {
		   res += -card[i];
	   }
   }
   cout << res;
}

发表于 2020-08-22 18:27:14 回复(0)
瀚海。头像 瀚海。 
// golang来一波
package main

import (
	"fmt"
	"sort"
)

func main() {
	n := 0
	_, _ = fmt.Scanf("%d\n", &n)
	a := make([]int, n)
	for i := 0; i< n; i++ {
	    _, _ = fmt.Scanf("%d", &a[i])
	}

	sort.Ints(a)
	fmt.Println(sumDiffScore(a))
}

func sumDiffScore(arr []int) int {
	sum := 0
	i := 0

	for i = len(arr) - 1; i > 0; i = i - 2 {
		sum += arr[i] - arr[i-1]
	}

	if i == 0 {
		sum += arr[0]
	}

	return sum
}


 

编辑于 2020-05-26 22:58:15 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 腾讯 排序 贪心 2018 Java工程师
上传者：小小
难度：
67条回答 17824浏览

热门推荐

通过挑战的用户

相关试题

纸牌游戏

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号