[HackerRank]ACM ICPC團隊(ACM ICPC Team)

題目描述

您將會得到要參加ACM-ICPC世界總決賽的N個參賽者的資料。每個參賽者都會精通或是不精通某些主題。若要將這N個參賽者分成兩人一隊，在這幾個隊伍中找出所有最多可以擅長幾項主題的隊伍，要能知道擅長主題和隊伍的數量。

假設a、b、c是不同的人，(a,b)和(b,c)是兩個不同的隊伍，也就是說同樣的人可以參加不同的隊伍。

原題網址

輸入格式

第一行包含兩個整數，N和M，用空格隔開。N的範圍在2到500之間(包含2和500)，為參賽者人數。M的範圍在1到500之間(包含1和500)，為主題的數量。

接下來的N行，每行表示每個參賽者擅長與不擅長的科目，會用一個長度為M的二進制數量來表示。如果第i行，第j個字元為1，則表示第i個參散者，擅長第j個主題，若為0就表示不擅長。

輸出格式

在第一行輸出所有的隊伍組合中，能夠擅長的最大主題數量。

在第二行輸出有幾個能夠擅長的最大主題數量的隊伍。

範例輸入

範例輸出

額外解釋

隊伍(1,3)和(3,4)都擅長5種主題。

解題概念

利用三層巢狀迴圈，來計算出各種隊伍組合所能擅長的主題數量。接著只需將所有的主題數量儲存下來，接著再進行排序之後，即可非常容易取得擅長主題數量的最大值，然後也可輕易計算出相同的最大值數量有多少個。

參考答案

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);
        final String first[] = sc.nextLine().split(" ");
        final int N = Integer.parseInt(first[0]);
        final int N_dec = N - 1;
        final int M = Integer.parseInt(first[1]);
        final char[][] know = new char[N][M];
        for (int i = 0; i < N; ++i) {
            know[i] = sc.nextLine().toCharArray();
        }

        final ArrayList<Integer> personTopic = new ArrayList<>();
        for (int i = 0; i < N_dec; ++i) {
            for (int j = i + 1; j < N; ++j) {
                int sum = 0;
                for (int k = 0; k < M; ++k) {
                    if (know[i][k] == '1' || know[j][k] == '1') {
                        ++sum;
                    }
                }
                personTopic.add(sum);
            }
        }
        final int personTopicSize_dec = personTopic.size() - 1;
        Collections.sort(personTopic);
        final int maxTopic = personTopic.get(personTopicSize_dec);
        int count = 1;
        for (int i = personTopicSize_dec - 1; i >= 0; --i) {
            if (personTopic.get(i) == maxTopic) {
                ++count;
            }
        }
        System.out.println(maxTopic);
        System.out.println(count);
    }
}