首页 > 试题广场 >

得分最大

[编程题]得分最大
  • 热度指数：401 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
牛牛和妞妞从他们的好朋友果果处得到了两个盒子，盒子里是一些写了分值的彩球。牛牛和妞妞发现两个盒子里的彩球数目是相等的，就决定一人一个。

妞妞拿到自己的盒子之后，决定跟牛牛玩一个游戏，规则如下：

一开始两个人盒子里的彩球数目都是n个，由妞妞先手，两人轮流实行下面两个操作中的一个（只能选其中一个执行，不能不执行。），直到两个盒子里的彩球都被拿完位置。

1、从自己的盒子里选一个球拿出来，把球上面的分值加在自己的总得分上边。
2、从对方的盒子里选一个球拿出来，把这个球移出游戏（对方不能再拿这个球）。

妞妞和牛牛都十分聪明，不会出错，并且尽可能让自己的得分比对方多。妞妞想知道，在游戏结束的时候，他能比牛牛多得多少分呢？

输入描述:
第一行一个数字n，表示盒子里初始彩球的数目。
第二行n个数字ai，表示妞妞盒子里第i个彩球的分值是ai。
第三行n个数字bi，表示牛牛盒子里第i个彩球的分值是bi。


输出描述:
一个整数ans，表示游戏结束的时候妞妞比牛牛多的分值。
示例1

输入

3
2 7 7
2 8 7

输出

0
示例2

输入

2
2 3
4 5

输出

-1

备注:
1<=n<=100000
1<=ai<=1000000
1<=bi<=1000000
算法知识视频讲解
添加回答
黄色变白色头像 黄色变白色
//scoreMax.cpp --得分最大
#include<iostream>
#include<algorithm>

using namespace std;

bool compare1(int a,int b)
{
return a > b;
}
void HandleData(vector<int>::iterator &it1,vector<int>::iterator &it2,int *count)
{
if(*it1 >= *it2)
{
*count = *count + *it1;
it1++;
}
else
{
it2++;
}
}


int main()
{
int n = 0;
int m = 0;
cin>>n;
vector<int> vec1;
vector<int> vec2;
    for(int i = 0;i<n;i++)
    {
    cin>>m;
        vec1.push_back(m);
}
    for(int i = 0;i<n;i++)
    {
    cin>>m;
        vec2.push_back(m);
}
    sort(vec1.begin(),vec1.end(),compare1);
    sort(vec2.begin(),vec2.end(),compare1);

    vector<int>::iterator it1 = vec1.begin();
    vector<int>::iterator it2 = vec2.begin();    
    int sum1 = 0,sum2 = 0;
    
    for(int i = 0;i < n;i++)
    {
    if(it1 != vec1.end() && it2 != vec2.end())
    {
        HandleData(it1,it2,&sum1);
            if(it1 != vec1.end() && it2 != vec2.end())
              HandleData(it2,it1,&sum2);
    else if(it1 != vec1.end())
                sum1 = sum1 + *it1;
            else if(it2 != vec2.end())
                sum2 = sum2 + *it2;
}   
else if(it1 != vec1.end())
            sum1 = sum1 + *it1;
        else if(it2 != vec2.end())
            sum2 = sum2 + *it2;
}

   cout<<sum1-sum2<<endl;


    return 0;
}
  
发表于 2019-07-08 21:06:03 回复(0)
已注销头像 已注销 
//基于快排的C语言解法
#include<stdio.h>

int partition(int a[],int left,int right)
{
    int i=left;
    int j=right;
    int temp=a[i];
    while(i<j)
    {
        while(i<j && a[j]>=temp)
            j--;
            if(i<j)
                a[i]=a[j];
        while(i<j && a[i]<=temp)
            i++;
            if(i<j)
                a[j]=a[i];
    }
    a[i]=temp;
    return i;
}
void quickSort(int a[],int left,int right)
{
    int dp;
    if(left<right)
    {
        dp=partition(a,left,right);
        quickSort(a,left,dp-1);
        quickSort(a,dp+1,right);
    }
}

int main(){
    int n = 0;
    scanf("%d",&n);
    int a[n],b[n];
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<n;i++)
        scanf("%d",&b[i]);
    int girl_score = 0;
    int boy_score = 0;
    //顺序排序
    quickSort(a,0,n-1);
    quickSort(b,0,n-1);
    /*
    拿一个自己的球会给自己加分，丢一个对手的求会给对手扣分，相当于给自己加了分，想要让自己的分数最高，策略就是：
    如果自己的球最大，拿起自己的球；如果对方的球最大，丢掉对方的球。
    */
    int i = n - 1;
    int j = n - 1;
    for(int round=0;round<n;round++){//一共n轮游戏
    //妞妞先来
        if(i>=0 && a[i] > b[j])//妞妞的最大，拿走这个
            girl_score += a[i--];
        else//牛牛的最大，丢掉这个
            j--;
    //牛牛来
        if(j>=0 && b[j] > a[i])//牛牛的最大，拿走这个
            boy_score += b[j--];
        else//妞妞的最大，丢掉这个
            i--;
    }
    printf("%d\n",(girl_score - boy_score));
    return 0;
}

发表于 2019-07-16 09:38:30 回复(2)
Java
紫气头像 紫气
严重怀疑是不是测试用例错了.🤐🤐🤐🤐
用例:
47
86 75 73 18 21 86 100 71 10 26 69 27 26 6 53 3 17 49 5 61 90 18 42 1 43 29 51 83 70 49 77 91 1 33 20 61 81 71 49 81 41 30 29 24 98 27 75
1 45 86 16 44 91 11 51 41 5 21 83 51 95 49 85 21 89 89 53 32 53 83 43 58 63 81 21 1 39 23 29 18 87 57 80 85 91 29 13 29 41 65 41 41 81 59
对应输出应该为:
-34
你的输出为:
-11 
public class ScoreBig {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int length = sc.nextInt();
        int[] aBox = new int[length];
        int[] bBox = new int[length + 1];
        for (int i = 0; i < aBox.length; aBox[i++] = sc.nextInt()) ;//运行不了的需要把赋值语句放到循环体里, 牛客网有不识别这种语法
        for (int i = 1; i < bBox.length; bBox[i++] = sc.nextInt()) ;
        Arrays.sort(aBox);
        Arrays.sort(bBox);
        int result = 0;
        for (int i = length - 1; i >= 0; i -= 2) result += aBox[i] - bBox[i];
        System.out.println(result);
    }
}

发表于 2019-07-09 15:00:12 回复(0)
雨亭1314头像 雨亭1314
importjava.util.*;
publicclassMain{
    publicstaticvoidmain(String[] args){
        Scanner sc=newScanner(System.in);
//while(sc.hasNext()){
          intN=sc.nextInt();
          int[] num1=newint[N];
          int[] num2=newint[N];
            for(inti=0;i<N;i++){
                num1[i]=sc.nextInt();
            }
            for(inti=0;i<N;i++){
                num2[i]=sc.nextInt();
            }
            Arrays.sort(num1);
            Arrays.sort(num2);
            intsum1=0;
            intsum2=0;
            for(inti=N-1;i>=0;i-=2){
                sum1+=num1[i];
            }
            for(inti=N-2;i>=0;i-=2){
                sum2+=num2[i];
            }
            intans=sum1-sum2;
          System.out.println(ans);
   //     }
 //   sc.close();
    } 
}

发表于 2019-06-22 11:12:23 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 数据库工程师 信息技术岗 贪心 区块链 模拟 测试开发工程师 2019 数学 大数据开发工程师 数据分析师 Java工程师 牛客
来自：2019校招-留学生招...
上传者：小小
难度：
4条回答 3594浏览

热门推荐

通过挑战的用户

相关试题

得分最大

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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