lightoj1198

maksyuki 发表于 oj 分类，标签: 基础算法-贪心

27 8月 2015

1198 - Karate Competition

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.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.

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

Output for Sample Input

424 76 2

6 2

4 7

5 10 1

10 7 1 4

15 3 8 7

Case 1: 4Case 2: 2Case 3: 4Case 4: 5

题目类型：贪心

算法分析：贪心策略是如果我最强比对方最强的能力高，则两者比；如果我最强的比对方最强的弱，则拿我队最弱的和对方最强的比；如果我最强的和对方最强的能力相同，则比较我队最弱的和对方最弱的，如果我队最弱的比对方最弱的强，则两者比；否则拿我最弱和对方最强的比

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 100 + 66;

int val_a[maxn], val_b[maxn];

int main()
{
//    ifstream cin ("aaa.txt");

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        cout << "Case " << flag++ << ": ";

        int n;
        cin >> n;

        for (int i = 0; i < n; i++)
            cin >> val_a[i];

        for (int i = 0; i < n; i++)
            cin >> val_b[i];

        sort (val_a, val_a + n, greater <int> ());
        sort (val_b, val_b + n, greater <int> ());

        int sum = 0, s_a = 0, e_a = n - 1, s_b = 0, e_b = n - 1, num = 0;

        while (num < n)
        {
            if (val_a[s_a] > val_b[s_b])
            {
                s_a++;
                s_b++;
                num++;
                sum += 2;
            }

            else if (val_a[s_a] == val_b[s_b])
            {
                if (val_a[e_a] > val_b[e_b])
                {
                    e_a--;
                    e_b--;
                    num++;
                    sum += 2;
                }

                else
                {
                    if (val_a[e_a] == val_b[s_b])
                        sum++;

                    e_a--;
                    s_b++;
                    num++;
                }
            }

            else
            {
                if (val_a[e_a] == val_b[s_b])
                    sum++;

                e_a--;
                s_b++;
                num++;
            }
        }

        cout << sum << endl;
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 100 + 66;

int val_a[maxn], val_b[maxn];

int main()

{

// ifstream cin ("aaa.txt");

int t, flag = 1;

cin >> t;

while (t--)

{

cout << "Case " << flag++ << ": ";

int n;

cin >> n;

for (int i = 0; i < n; i++)

cin >> val_a[i];

for (int i = 0; i < n; i++)

cin >> val_b[i];

sort (val_a, val_a + n, greater <int> ());

sort (val_b, val_b + n, greater <int> ());

int sum = 0, s_a = 0, e_a = n - 1, s_b = 0, e_b = n - 1, num = 0;

while (num < n)

{

if (val_a[s_a] > val_b[s_b])

{

s_a++;

s_b++;

num++;

sum += 2;

}

else if (val_a[s_a] == val_b[s_b])

{

if (val_a[e_a] > val_b[e_b])

{

e_a--;

e_b--;

num++;

sum += 2;

}

else

{

if (val_a[e_a] == val_b[s_b])

sum++;

e_a--;

s_b++;

num++;

}

else

{

if (val_a[e_a] == val_b[s_b])

sum++;

e_a--;

s_b++;

num++;

}

cout << sum << endl;

}

return 0;

}

lightoj1197

lightoj1202

一	二	三	四	五	六	日
« 6月
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

超客的水墨烟雨

lightoj1198

Input

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论