04005: 拼点游戏

greedy, http://cs101.openjudge.cn/practice/04005

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

输入

输入包含多组测试数据。每组测试数据的第一行是一个整数n(1<=n<=1000)，接下来一行是n个整数，表示C抽到的白色卡牌的点数，下一行也是n个整数，表示S抽到的蓝色卡牌的点数。输入的最后以一个0表示结束。

输出

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

样例输入

样例输出

9 5
4 4
4 4

思路：田忌赛马

python

def get_max_profit(a1, a2):
    la1 = 0
    ra1 = len(a1) - 1
    la2 = 0
    ra2 = len(a2) - 1
    ans_max = 0
    ans_min = 0

    while la2 <= ra2:
        if a2[la2] > a1[la1]:
            ans_max += 3
            ans_min += 1
            la1 += 1
            la2 += 1
        elif a2[ra2] > a1[ra1]:
            ans_max += 3
            ans_min += 1
            ra1 -= 1
            ra2 -= 1
        else:
            if a2[la2] < a1[ra1]:
                ans_max += 1
                ans_min += 3
            elif a2[la2] == a1[ra1]:
                ans_max += 2
                ans_min += 2

            la2 += 1
            ra1 -= 1

    return ans_max, ans_min


while True:
    n = int(input())
    if n == 0:
        break

    *C, = map(int, input().split())
    *S, = map(int, input().split())
    C.sort()
    S.sort()

    ans_max, _ = get_max_profit(C, S)
    _, ans_min = get_max_profit(S, C)

    print(ans_max, ans_min)

04005: 拼点游戏 ​

04005: 拼点游戏