[白俊]2831号:舞踏会

https://www.acmicpc.net/problem/2831

問題の説明

の数字nが与えられる.

列目はn人の男の身長を与えた.

列3列目はn人の女性の身長を与えた.

キーは、倹約値が1500以上2500以下の整数です.人の身長は代価だ.

男子の身長が正数なら、自分より背の高い女子と踊りたい男子、負数なら背の低い女子と踊りたい男子です.

女子の身長が正数なら自分より背の高い男子と踊りたい女子、負数なら背の低い男子と踊りたい女子です.

このような条件を持って、私はあなたにダンスのペアを作ってあげたいです.最大何組までできるのでしょうか?

入力例
2
-1800 -2200
1900 1700
上記の場合、男子−2200は女子1900と男子−1800と女子1700とペアを組むとよい.

アルゴリズム#アルゴリズム#

まず、正数の男と負数の女、負数の男の正数の男だけがマッチングできるので、別々に並べます.
男とbpの負数を譲られる男
譲り受けた女性をgp負数の女性にgnという配列に格納する.
(bp,gn)と(gp,bn)はできるだけ多くマッチングしなければならない.つまり
bp,gnを求める要素の和が負数の順対である最大個数に等しい.
できるだけ多くマッチングする方法は

正数配列直接並べ替え、負数配列逆並べ替え.(絶対値ソート)

bp,gnの最後の要素の和が負数の場合

と一致しました.

両方とも最後の要素pop

count++

0以上

正数の大きさが大きすぎたので一致しませんでした.

は羊水だけを弾き出す.

bp,gnの2つのうちの1つは,空になるまで2を繰り返すとgp,bnに対しても2を行う.

コード#コード#

import sys
def conditionalCounter(boysOrGirlsPostive,girlsOrBoysnegative):
    postive=boysOrGirlsPostive
    negative=girlsOrBoysnegative
    def counter():
        count=0
        while postive and negative:
            if postive[-1]+negative[-1]<0:
                count+=1
                postive.pop()
                negative.pop()
            else:
                postive.pop()
        return count
    return counter
    
if __name__ == "__main__":
    input()

    boys=list(map(int,sys.stdin.readline().rstrip().split()))
    girls=list(map(int,sys.stdin.readline().rstrip().split()))

    boysPostive=sorted([i for i in boys if i>0])
    boysNegative=sorted([i for i in boys if i<0],reverse=True)
    girlsPostive=sorted([i for i in girls if i>0])
    girlsNegative=sorted([i for i in girls if i<0],reverse=True)

    bpgn=conditionalCounter(boysPostive,girlsNegative)
    gpbn=conditionalCounter(girlsPostive,boysNegative)

    print(bpgn()+gpbn())

チップ

関数の戻り値で内部関数を返す関数を高次関数のclosureと呼ぶ.
closureを使用する利点は、不変のパラメータを内部関数に直接バインドし、パラメータの数を減らすことです.
上記の関数ではconditionalCounterがpostiveと負の値を直接選択してバインドするため、不変のパラメータは伝達されないbpgn関数とgpbn関数を作成することができる.