Luogu P1068 [NOIP2009 popularity group] score line delineation [simulation - sorting]

Title Description

The selection of Expo volunteers is in full swing in city A. In order to select the most suitable talents, city a has conducted a written test for all the applicants. Only those whose written test scores reach the interview score line can enter the interview. The interview score line is defined according to 150 \% of the planned enrollment, that is, if mm volunteers are planned to be enrolled, the interview score line is ranked m × The scores of 150% (rounded down) contestants, and the contestants who finally enter the interview are all those whose written test scores are not lower than the interview score line.

Now please write a program to delimit the interview score line, and output the registration number and written test results of all contestants entering the interview.

Input format

First line, two integers   n. M (5 ≤ n ≤ 5000, 3 ≤ m ≤ n), separated by a space, where nn represents the total number of contestants registered for the written examination, and M represents the number of volunteers planned to be admitted. Input data guarantee M × Less than or equal to 150% rounded down   n.

Second line to second line   n+1n+1   Lines, each line includes two integers separated by a space, which are the contestant's registration number   k(1000 ≤ k ≤ 9999) and the contestant's written test score s(1 ≤ s ≤ 100). The data ensure that the registration numbers of contestants are different.

Output format

In the first line, there are 2 integers separated by a space. The first integer represents the interview score line; The second integer is the actual number of contestants entering the interview.

Starting from the second line, each line contains two integers separated by a space, which respectively represent the registration number and written test scores of the contestants entering the interview. They are output from high to low according to the written test scores. If the scores are the same, they are output from small to large according to the registration number.

Input and output samples

Enter #1 copy

6 3 
1000 90 
3239 88 
2390 95 
7231 84 
1005 95 
1001 88

Output #1 copy

88 5 
1005 95 
2390 95 
1000 90 
1001 88 
3239 88 

Description / tips

[example description]

m \times 150\% = 3 \times150\% = 4.5m × 150%=3 × 150% = 4.5, rounded down to 44. The score line for 44 people to enter the interview is 8888, but because 8888 has heavy scores, all scores are greater than or equal to 8888   All the contestants can enter the interview, so 55 people finally enter the interview.

Question 2 of NOIP 2009 popularity group

analysis:

This question mainly focuses on sorting. The registration number and score can be stored by defining a student class (similar to the structure) or a two-dimensional array. Here, the student class is used, and then the sorting class is customized. If the scores are the same, they are arranged in ascending order according to the registration number, and if the scores are different, they are arranged in descending order according to the scores.

The source code is attached below

​
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner in  = new Scanner(System.in);
        int i =0;
        int n = in.nextInt();
        int m = in.nextInt();
        int count = (int) (m*1.5);//Number of people planned to enter the interview
        int sum = count;//Used to output the number of people who finally enter the interview
        Interview[] stu = new Interview[n];
        for ( i = 0; i < n; i++) {
            int number = in.nextInt();
            int score = in.nextInt();
            stu[i] = new Interview(number,score);
        }
        Arrays.sort(stu,new compare());

        while (stu[sum-1].score==stu[sum].score){//If the number of planned entrants has been reached, because if the score is the same as that of the last person, they will also enter the interview together
            sum++;
        }
        System.out.println(stu[sum-1].score+" "+sum);//Because the array subscript starts from 0, the subscript of the last person is sum-1
        for ( i = 0; i < sum; i++) {
            System.out.println(stu[i].number+" "+stu[i].score);
        }
    }
}
//Define an interview member class, similar to a structure
class Interview{
    int number;
    int score;

    public Interview(int number, int score) {
        this.number = number;
        this.score = score;
    }
}
//Define sort class
class compare implements Comparator<Interview> {
    @Override
    public int compare(Interview o1, Interview o2) {
        if (o1.score==o2.score)
            return o1.number-o2.number;//In ascending order of student number
        return o2.score-o1.score;//In descending order of scores
    }
}

​

This is the first yellow question solution written by konjaku, which will be updated continuously in the future. I also hope you can give me more support.

Keywords: Java Permutation

Added by Undrium on Sun, 05 Dec 2021 11:04:22 +0200