DC05-01-01-拼点游戏

大家好，欢迎来到IT知识分享网。

题目描述

C和S两位同学一起玩拼点游戏。有一堆白色卡牌和一堆蓝色卡牌，每张卡牌上写了一个整数点数。C随机抽取n张白色卡牌，S随机抽取n张蓝色卡牌，他们进行n回合拼点，每次两人各出一张卡牌，点数大者获得三颗巧克力，小者获得一颗巧克力，如果点数相同，每人各得二颗巧克力，使用过的卡牌不得重复使用。已知C和S取到的卡牌点数，请编程计算S最多和最少能得到多少颗巧克力。

输入格式

输入包含多组测试数据。

每组测试数据的第一行是一个整数n(1<=n<=1000)，接下来一行是n个整数，表示C抽到的白色卡牌的点数，下一行也是n个整数，表示S抽到的蓝色卡牌的点数。

输入的最后以一个0表示结束。

输出格式

对每组数据，输出一行，内容是两个整数用空格格开，分别表示S最多和最少可获得的巧克力数。

输入输出样例

输入 #1

3 92 83 71 95 87 74 2 20 20 20 20 2 20 19 22 18 0

输出 #1

9 5 4 4 4 4

解析：

    整个题给我的感觉就是有点像 田忌赛马 ，咱还是用贪心去做。

还是用田忌赛马的方法，比较最大的牌，如果S最大的牌比

C最大的牌数值要大那就和C最大的牌成一对，获得3颗巧克力，

不然就用最小的与最小的比较具体如下：

if(b[y]>a[x]){ max+=3; y--; x--; }else{ if(b[j]>a[j]){ max+=3; i++; j++; }else{ if(b[j]==a[x]){ max+=2; j++; x--; }else{ max++; j++; x--; } } }

用一个函数封装起来

int f(int a[],int b[],int n){ int maxn=0,i=0,j=0,x=n-1,y=n-1; while(i<=x&&j<=y){ if(b[y]>a[x]){ maxn+=3; y--; x--; }else{ if(b[j]>a[j]){ maxn+=3; i++; j++; }else{ if(b[j]==a[x]){ maxn+=2; j++; x--; }else{ maxn++; j++; x--; } } } } return maxn; }

成品：

#include<bits/stdc++.h> using namespace std; int f(int a[],int b[],int n){ int ans=0,i=0,j=0,x=n-1,y=n-1; while(i<=x&&j<=y){ if(b[y]>a[x]){ ans+=3;y--;x--; }else{ if(b[j]>a[j]){ ans+=3;i++;j++; }else{ if(b[j]==a[x]){ ans+=2;j++;x--; }else{ ans++;j++;x--; } } } } return ans; } int main(){ long long n=1; while(n!=0){ cin>>n; long long a[n+10]={0}; long long b[n+10]={0}; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i]; sort(a+1,a+1+n); sort(b+1,b+1+n); int maxn=f(a,b,n); int minn=4*n-f(b,a,n); cout<<maxn<<" "<<minn<<endl; } return 0; }