質問する

いつでも最高の大企業陣営の株式会社だけを求めて新入社員募集を実施する.人材選抜試験は第1回書類審査と第2回面接からなる.最高の企業理念だけを追求し、最も優秀な人材を従業員として選抜したいと考えています.
そのため、珍栄株式会社は、他のすべての応募者に比べて、書類審査成績と面接成績のうち少なくとも1人が他の応募者を下回らないという原則を制定した.つまり、ある応募者Aの成績が他の応募者Bの成績に比べて書類審査の結果も面接の成績も低下すれば、Aは絶対に選ばれないということです.
これらの条件を満たす場合は、珍栄株式会社が今回の新入社員募集で選抜できる新入社員の最大人数を要求する計画を立ててください.

入力

第1行は、試験例の個数T(1≦T≦20)を与える.各試験例の最初の行は、ボランティアの数N(1≦N≦100000)を与えた.2行目からN行目では、応募者ごとの書類審査成績、面接成績の順位が空白で1行になっています.どちらの成績順も1位からN位までは上下しないと仮定している.

しゅつりょく

各テストケースについて、珍栄株式会社は新入社員の最大人数を1行1行印刷することができます.

に答える

この問題は多くの時間をかけて問題を理解した.まず、ファイルランキングと面接ランキングを入力することに注意してください.
選抜できる新入社員の最大人数を探すべきで、質問で他の応募者の書面成績や面接成績より優れていれば、新入社員になれる.では、どのようにして最大人数を獲得しますか?
まず、書類や面接の順番に並べ替えます.筆者は,文書順に面接順を並べた1次元配列を用いた.理由は入力条件が前後を問わないため、同じ順序は考慮する必要はありません.
現在書類ランキング1位の人はどう見ても入社者なので2位から確認すればいいです.この場合の比較基準は、すでに入社が決まっている人の中で、面接の順位が高いということです.
質問N=5の場合の例(ファイルランキング,面接ランキング),入力は(3,2),(1,4),(4,1),(2,3),(5,5)である.書類順に並べると(1,4),(2,3),(3,2),(4,1),(5,5)となりますが、この場合(1,4)が書類ランキング1位となるので、入社が決まります.
今は(2,3)から比較すればいいので、(1,4)よりも面接順位が高い(3<4)ので(2,3)入社も決まっています.標準は3に変更されます.次に(3,2)が(2,3)の面接より順位が高いので、この人も確定します.(4,1)面接で1位だったので無条件で確定.最後(5,5)は全員の中で最下位なので、入社できません.

ソース

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int t = Integer.parseInt(br.readLine());

		while (t-- > 0) {
			int n = Integer.parseInt(br.readLine());
			// 서류 순위에 따른 면접 순위 저장 배열
			int[] arr = new int[n + 1];

			for (int i = 0; i < n; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				arr[a] = b;
			}

			// 1등은 무조건 입사
			int count = 1;
			// 1등의 면접 순위
			int rank = arr[1];

			for (int i = 2; i <= n; i++) {
				// 현재 면접 순위가 이전 면접순위보다 작다면 (더 높은 순위라면)
				if (arr[i] < rank) {
					count += 1;
					rank = arr[i];
				}
			}

			System.out.println(count);

		}
		br.close();

	}

}