[白俊]2458キー順

📌 質問する

1番からN番まで番号が貼られていた生徒について、2人の生徒の身長を比較し、結果の一部を得た.しかし、N人とも身長が異なると仮定する.例えば、6人の生徒に対して身長を6回しか比較しなかった結果、以下のようになった.

1番学生の身長<5番学生の身長

3番学生の身長<4番学生の身長

5番学生の身長<4番学生の身長

4番学生の身長<2番学生の身長

4番学生の身長<6番学生の身長

5番学生の身長<2番学生の身長

この比較結果から、すべての生徒の中で、一番背の小さい生徒から自分が何位であるかを知ることができ、以下のような図を描いて自分が何位であるかを簡単に確認することができる.a番学生の身長がb番学生の身長より小さい場合は、aからbまでの矢印で表します.

1番は5番より低く、5番は4番より低いので、1番は4番より低いです.では、1番、3番、5番はいずれも4番未満です.また、4番が2番と6番より小さいので、4番には自分より小さい学生が3人、自分より大きい学生が2人いて、自分の身長が何位なのか正確に知ることができます.しかし、4番以外の生徒たちは自分の身長がどれくらいなのか分からない.
学生の身長を比較するときは、自分の身長を知っている学生が何人いるかを計算し、プログラムを書いてください.

✔方法

プログラマーのランキング題と解答方法は同じです.

1は5より大きい.そして5対4の大きさ1は4より大きい.

1は5未満です.そして5対4で小さい->1は4未満です.

以上の2つの場合を考慮して,3つの複文を用いてコードを記述することができる.

✔コード

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[][] graph = new int[n][n];
		int result = 0; 
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(i == j) graph[i][j] = 0;
				else graph[i][j] = (int)1e9;
			}
		}
		
		for (int i = 0; i < m; i++) {
			int x = sc.nextInt() - 1;
			int y = sc.nextInt() - 1;
			graph[x][y] = -1;
			graph[y][x] = 1;
		}

		for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if(graph[i][j] == (int)1e9) {
						if(graph[i][k] == 1 && graph[k][j] == 1)
							graph[i][j] = 1;
						if(graph[i][k] == -1 && graph[k][j] == -1)
							graph[i][j] = -1;
					}
				}
			}
		}
		

		
		for(int i = 0; i < n; i++) {
			int count = 0;
			for(int j = 0; j < n; j++) {
				if(graph[i][j] == (int)1e9) count++;
			}
			if(count == 0)
				result++;
		}
		
		System.out.println(result);
	}
}

ソース:https://www.acmicpc.net/problem/2458