白駿(7568号)-大金持ち

質問元:https://www.acmicpc.net/problem/7568
質問する

私たちは身長、体重、この2つの値で人の塊を測ってみました.体重がxkg、身長がycmの人がいれば、その人の体は(x,y)で表されます.2人のAとBのブロックがそれぞれ(x,y),(p,q)の場合,x>pとy>qの場合,AのブロックはBのブロックより「大きい」と述べた.例えば、A、Bの2人のブロックがそれぞれ(56、177)、(45、165)である場合、AのブロックはBより大きいものに相当する.しかし、大きさが決められない場合もあります.例えば、2人のCとDのブロックがそれぞれ(45、181)、(55、173)であれば、体重DはCより重く、身長Cが高いので、「ブロック」だけでは、CとDは誰も相手より高いとは言えない.

N個人のグループでは,一人一人のブロックレベルが自分よりも大きいブロックとして定められている.自分より大きい人にk人がいれば、その人のブロック等号はk+1です.このように等級を決めると、同じブロックの等級の人が何人もいます.以下は5人で構成された集団の中の一人一人の塊とその等号の表です.

名前.
(体重、身長)
かたまり
A
(55, 185)
2
B
(58, 183)
2
C
(88, 186)
1
D
(60, 175)
2
E
(46, 155)
5

表でCより大きい人はいないのでCが1位です.しかも、A、B、Dより大きいのはCだけなので、2位です.またEより大きい人はA B C Dのような4人なのでEの塊は5位上記の場合、3位と4位は存在しない.皆さんはN名の生徒の体重と身長の入力を読んで、一人一人の体の等号を計算します.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    private static class Person {

        int weight;
        int height;

        public Person(int weight, int height) {
            this.weight = weight;
            this.height = height;
        }

        public boolean isBig(Person person) {
            return (this.weight > person.weight && this.height > person.height);
        }
        
    }

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

        int N = Integer.parseInt(reader.readLine()); // 전체 사람의 수

        Person[] people = new Person[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            people[i] = new Person(Integer.parseInt(tokenizer.nextToken()), Integer.parseInt(tokenizer.nextToken()));
        }

        for (int i = 0; i < N; i++) {
            int cnt = 0;
            for (int j = 0; j < N; j++) {
                if (people[j].isBig(people[i])) cnt++;
            }

            sb.append(cnt + 1).append(" ");
        }

        System.out.println(sb);
    }

}

は最初にソートを用いて解くことを試みたが,出力順序は入力順序と同じであるため,比較サイズの方法を作成するだけで解決した.

のわずかな違いですが、オブジェクトの作成よりも配列を使用する方が早いようです.