題目描述
您將會得到要參加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就表示不擅長。
輸出格式
在第一行輸出所有的隊伍組合中,能夠擅長的最大主題數量。
在第二行輸出有幾個能夠擅長的最大主題數量的隊伍。
範例輸入
4 5
10101
11100
11010
00101
10101
11100
11010
00101
範例輸出
5
2
2
額外解釋
隊伍(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);
}
}