题解 | #[NOIP2007]奖学金#【自用笔记】
[NOIP2007]奖学金
https://ac.nowcoder.com/acm/problem/16639
思路
这题需要我们重点关注的三个值:语数英总分、语文成绩、学号
整体思路
- 根据题意可以得知,上述三个需要重点关注的值,对排名影响的权重排列是:三科总分 > 语文成绩 > 学号;
我们先暂时抛开这题,假设我们现在需要找出两个三位数中较大的那一个,你会怎么找?
- 先对比它们俩 百位上的数值,如果存在二者中的一个比另外一个要大,那么你肯定不会再继续往下比较十位和个位上的数值了;
- 因为百位数值大小已经确定,那么无论十位和个位的数值大小关系是怎么样的,都不可能影响到最终的结果了;
- 而如果它两百位数值相同,那你一定会继续去比较二者十位上的数值,如果十位能分出大小,那么最终结果就确定了,如果分不出大小你会再比较个位上的数字;
到这里,你应该能感觉到,这个比较两个3位数的过程其实和我们这题差不多:
- 先比较三科总分,能分出大小,那最终结果就确定了;分不出大小就要继续比较下一个“决定因素”
- 因此我们可以把这题我们需要重点关注的三个值构成一个整数,直接对这个组合而成的整数排序,就可以得到答案
注意点
- 按照题意,一个人的三科总分、语文成绩越高越好;但是它的学号越大反而不利于提升它的排名
- 因此在把三个重点关注的值组合成一个整数的过程中,我们往里组合的不应该是学号本身,而应该是总人数减去学号
代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int man = sc.nextInt();
long[] stds = new long[man];
for (int i = 0; i < man; i++) {
long score = 0;
int chinese = sc.nextInt();
score += chinese;
score += sc.nextInt();
score += sc.nextInt();
stds[i] = score * 1000000 + chinese * 1000 + 300 - i;
}
Arrays.sort(stds);
for (int i = man - 1; i >= man -5 ; i--) {
long id = 300 - stds[i] % 1000;
long score = stds[i] / 1000000;
System.out.println((id + 1) +" "+score);
}
}
}