[2461]代表選手
import java.util.*;
import java.io.*;
public class Main {
static int N, M, answer;
static Group[] gArr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
gArr = new Group[N*M];
answer = 1000000000;
int s = 0;
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
gArr[s++] = new Group(i,Integer.parseInt(st.nextToken()));
}
}
Arrays.sort(gArr);
fn();
System.out.println(answer);
}
static void fn() {
//왼쪽 오른쪽 시작 지점, 구간 안에 포함된 반의 개수를 담을 변수
int rv=0, lv=0, cnt=0;
//왼쪽 포인터의 최대 거리
int max = M*N-N;
//오른쪽 포인터의 최대 거리
int end = M*N;
//구간에 반별 몇명이 포함되어 있는지 확인할 변수
int check[] = new int[N];
//왼쪽 포인터가 최고 거리 도달 할때 까지 반복
while(lv<max) {
//구간에 포함된 반의 수가 N보다 작을 경우 반복
while(cnt<N) {
//오른쪽 포인터가 끝에 도달하면 함수 종료
if(rv==end) return;
int num = gArr[rv++].num;
//구간에 자신과 같은 반인 사람이 없는 경우
if(check[num] == 0) {
//지금까지 포함된 반의 갯수++
cnt++;
}
//구간에 포함된 같은 반의 명수를 나타내는 check++
check[num]++;
}
//왼쪽 포인터에서 한칸 전진했을 때 그 사람이 같은 반이라면
while(lv<max && gArr[lv].num == gArr[lv+1].num) {
//구간에 포함된 자신과 동일한 반의 명수 --;
check[gArr[lv++].num]--;
}
answer = Math.min(answer, gArr[rv-1].score-gArr[lv].score);
//만약 자신이 빠졌을때 같은 반을 가진 사람이 0명이라면
if(--check[gArr[lv++].num]==0) {
cnt--;
}
}
}
//반과 점수를 가지는 객체
static class Group implements Comparable<Group>{
int num;
int score;
public Group(int num, int score) {
super();
this.num = num;
this.score = score;
}
public int compareTo(Group g) {
return score-g.score;
}
}
}
他人を解く
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
private static PriorityQueue<Student> pq = new PriorityQueue<>();
private static class Student implements Comparable<Student>{
int index;
int value;
public Student(int index, int value) {
this.index = index;
this.value = value;
}
@Override
public int compareTo(Student s) {
return this.value - s.value;
}
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] students = new int[2_000][2_000];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
Arrays.fill(students[i], Integer.MAX_VALUE);
for(int j = 0; j < M; j++) {
students[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(player(N, M, students));
}
private static int player(int n, int m, int[][] arr) {
int[] pos = new int[n];
int result = Integer.MAX_VALUE;
int max = class1Classify(n, arr);
int loop = n * m;
while(loop-- > 0) {
//가장 작은 점수를 가지는 학생 리턴
Student current = pq.poll();
//둘중 가장 작은 차이를 result에 저장
result = Math.min(result, max - current.value);
//현재 학생의 반에서 빠진 학생의 수 ++
pos[current.index]++;
//현재 학생의 반에서 빠진 학생의 수가 N과 같을 경우 탈출
if(pos[current.index] == n) break;
//현재 빠진 학생의 반에서 빠진 학생 다음으로 점수가 높은 학생을
//대려와 원래 있던 max와 점수를 비교하여 큰 걸 max에 넣음
max = Math.max(max, arr[current.index][pos[current.index]]);
//대려왔으니 pq에 넣는다.
pq.offer(new Student(current.index, arr[current.index][pos[current.index]]));
}
return result;
}
//반 별 오름차순 정렬 후 각 반의 제일 작은값 중에서 제일 큰 값을 가진 반의 값을 max로 반환
private static int class1Classify(int n, int[][] arr) {
int max = 0;
for(int i = 0; i < n; i++) {
Arrays.sort(arr[i]);
max = Math.max(max, arr[i][0]);
pq.offer(new Student(i, arr[i][0]));
}
return max;
}
}
Reference
この問題について([2461]代表選手), 我々は、より多くの情報をここで見つけました https://velog.io/@away0419/2461대표-선수テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol