Karate Competition（贪心）

admin管理员组

文章数量:1529448

                                                                                         Karate Competition Time Limit:2000MS     Memory Limit:32768KB     64bit IO Format:%lld & %llu Submit  Status

Description

Your karate club challenged another karate club in your town. Each club enters N players into the match, and each player plays one game against a player from the other team. Each game that is won is worth 2 points, and each game that is drawn is worth 1 point. Your goal is to score as many points as possible.

Your secret agents have determined the skill of every member of the opposing team, and of course you know the skill of every member of your own team. You can use this information to decide which opposing player will play against each of your players in order to maximize your score. Assume that the player with the higher skill in a game will always win, and if the players have the same skill then they will draw.

You will be given the skills of your players and of the opposing players, you have to find the maximum number of points that your team can score.

Input

Input starts with an integer T (≤ 70), denoting the number of test cases.

Each case starts with a line containing an integer N (1 ≤ N ≤ 50). The next line contains N space separated integers denoting the skills of the players of your team. The next line also contains N space separated integers denoting the skills of the players of the opposite team. Each of the skills lies in the range [1, 1000].

Output

For each case, print the case number and the maximum number of points your team can score.

Sample Input

4

2

4 7

6 2

2

6 2

4 7

3

5 10 1

5 10 1

4

10 7 1 4

15 3 8 7

Sample Output

Case 1: 4

Case 2: 2

Case 3: 4

Case 4: 5

重点内容**题意 给定双方的n个数字，如果a比b大两分，平1分，输了不得分，问a最多多少分。

思路 a队从小到大找到每个队员能pk的最大技能的对手，这样能找到赢得最大数目漏下的就是平的对手，加上就行```

#include<bits/stdc++.h>
using namespace std;
int a[77];
int b[77];
int main()
{
    int t;
    scanf("%d",&t);
    int cas=1;
    while(t--)
    {
        int n;
        int i,j,sum=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
         for(int i=0;i<n;i++)
        {
            scanf("%d",&b[i]);
        }
        sort(a,a+n);
        sort(b,b+n);
        for(i=0;i<n;i++)
        {
            for(j=n-1;j>=0;j--)
            {
                if(b[j]==-1)
                    continue;
                if(a[i]>b[j])//找到小的可以赢得最大的情况
                    break;
            }
            if(j==-1)//已经比完啦
                continue;
            sum+=2;
            b[j]=a[i]=-1;//标记已经比过啦
        }
        for( i=0;i<n;i++)
        {
            if(a[i]==-1)
                continue;
            for(j=0;j<n;j++)
            {
                if(b[j]==-1)
                    continue;
                if(a[i]==b[j])//找到平的
                {
                    sum++;
                    b[j]=a[i]=-1;
                }
            }
        }
        printf("Case %d: %d\n",cas++,sum);
    }
}

本文标签： 贪心Karatecompetition