プログラマー-デジタルゲーム

1.質問

質問リンク
説明:
xx社の2 xN名の従業員は2つのグループに分けられ、各グループはN名である.二つのチームはAチームとBチームです.デジタルゲームのルールは以下の通りです.

まず、すべての従業員に自然数がランダムに割り当てられます.

従業員1人につき1回しか試合をしません.

試合ごとにA組に1人の従業員がいて、B組に1人の従業員がいて、お互いの人数を公開します.そのとき数字の大きい方が勝ち、勝った社員が所属するチームが1点を取る.

同じ数字であれば、誰もポイントを得ることはできません.

従業員全員がまずランダムに自然数を割り当てられた.そしてAチームはすぐに出場順を決め、自分の出場順をBチームに公開した.Bチームはそれを見て、自分の最終ポイントが一番高い方法で選手たちの出場順を決めた.この時Bチームが獲得したポイントを見つけてください.
A組メンバーに付与された数参加順に並べられた配列Aとi組要素がB組のi組メンバーに付与された数の配列Bである場合は、解題関数を完了し、B組メンバーが得られる最大ポイントを返すようにしてください.
せいげんじょうけん

AとBの長さは同じです.

AおよびBの長さは1または100000未満である.

AおよびBの各要素の自然数は、1または10000000未満である.

I/O例
ABresult[5,1,3,7][2,2,6,8]3[2,2,2,2][1,1,1,1]0
I/O例説明

2.解答

ざっと近づくBのすべてのチームメンバーをリストするだけです.
最大スコアを取得する方法.
ただし、チームメンバーがリストされている場合は、N!です.
组员最多100,000人、ないでしょう...
非常に近い
簡単に考えてみましょう.
そのため,一つの仮定によって証明する.
命題-Bチームが最大点数を獲得するには、Aチームの高数字Bチームの高数字をカバーしなければならない.
直観的には当たり前ですが、帰入法で近づけると、
仮に,Aチームの低得点をBチームの高得点に上書きすると,最大点数が得られる.
矛盾--Aチームの低得点をBチームの低得点にカバーすると、より高い点数が得られます.
たとえばA = [11, 2, 2], B = [13, 3, 3]の場合、A上の2はB上の13に覆われ、点数は2である.A上の2がB上の3に上書きされた場合、スコアは3である.
まず良い武器を手に入れたでは、どのようにしてその上で実施するのでしょうか.
この問題は、直接ソートおよびダブルポインタO(N)によってのみ解決できます.
実際、Aのチームメンバーの順序は固定されているため、調整する必要はありません.
最高点数を得るためには、AチームメンバーをBと一対一にマッチングさせることが重要です.
次に、AおよびBを降順に並べます.

A.sort((a, b) => b - a);
B.sort((a, b) => b - a);

今まで手に入れた武器(灰色で獲得した命題に近づく)を
2つのポインタに関連付けられて実装されます.

let j = 0; // B를 가리키는 인덱스
let ans = 0; // 점수

for (let i = 0; i < A.length; i++) { // i는 A를 가리키는 인덱스
    if (A[i] < B[j]) { // B가 더 클 때 
        ans++; // 점수 증가
        j++; // B를 가리키는 인덱스 증가
    }
}

以前に入手した武器によれば、Aの高い数値はBの高い数値をカバーすることが望ましい.
現在のBチームメンバーが所有している数値.Aチームメンバーの数を上書きできる場合、スコアが増加します.
不可能なら、後ろの選手も点数を取ることはできない.
すべてのチームメンバーの数を表示するまで、この手順を繰り返します.

3.完全なコード

function solution(A, B) {
    A.sort((a, b) => b - a);
    B.sort((a, b) => b - a);

    let j = 0; // B를 가리키는 인덱스
    let ans = 0; // 점수

    for (let i = 0; i < A.length; i++) { // i는 A를 가리키는 인덱스
        if (A[i] < B[j]) { // B가 더 클 때 
            ans++; // 점수 증가
            j++; // B를 가리키는 인덱스 증가
        }
    }

    return ans;
}

この問題のレベルは3です.
私は見るとすぐに答えが思いつくので簡単に解決できる問題です
個人的にはレベル2の難題がもっと多いと思います
難易度は相対的なので、レベルを問わず問題を解く姿勢が必要です.