有一个班级有 n 个人，给出 n 个元素，第 i 个元素代表 第 i 位同学的考试成绩，接下进行 m 次询问，每次询问给出一个数值 t ，表示第 t 个同学，然后需要我们输出第 t 个同学的成绩超过班级百分之几的人，百分数 p 可以这样算：p = (不超过第 t 个同学分数的人数 ) / n * 100%。输出的时候保留到小数点后 6 位，并且需要四舍五入。
输入描述：第一行输入两个数 n 和 m，两个数以空格隔开，表示 n 个同学和 m 次询问。第二行输入 n 个数值 ni，表示每个同学的分数，第三行输入 m 个数值mi，表示每次询问是询问第几个同学。（注意，这里 2<=n，m<=100000，0<=ni<=150，1<=mi<=n）
输出描述：输出 m 行，每一行输出一个百分数 p，代表超过班级百分之几的人。
示例1：
输入 ：
3 2
50 60 70
1 2
输出
33.333333%
66.666667%
一开始我的思路是，先将 scores 数组排序，这样就能很容易算出 “有多少人不超过当前分数” 这个前缀和。但如果要将 scores 排序的话，还得另外记录 “第 mi 位同学” 排序后是第几位，这样就很麻烦，一点都不优雅。
今天看到 lucifer 的公众号推文后，才发现原来可以把“分数”这个值本身当作数组下标啊，所以思路就变成了：
- 因为
分数的范围是[0, 150]，所以我们可以用一个长度为 150 的数组prefix来记录每个分数出现的次数，数组下标是分数值，数组的值就是分数出现的次数； - 遍历
scores数组，对于每个分数s，prefix[s]++； - 遍历
prefix，计算前缀和； - 然后我们就可以实现
$O(1)$ 时间的：- 询问第
mi位同学的分数能超过班上百分之几的人 - 通过
scores[mi]找到这位同学的分数s - 通过
prefix[s]找到不超过分数s的人数 - 算数学吧
- 询问第
- 时间复杂度：$O(N)$，N 是数组长度。
- 空间复杂度：$O(max(scores))$，前缀和数组，取决于分数范围。
JavaScript Code
/**
* @param {number[]} scores 全班同学的分数
* @param {number} mi 第 mi 个同学
* @return {number} 第 mi 个同学的分数能超过班级百分之几的人
*/
var test = function (scores, mi) {
// 下标是分数，值是“有多少人是这个分数”
const prefix = Array(151).fill(0);
// 先遍历 scores 数组，统计每个分数的人数
scores.forEach(s => prefix[s]++);
// 计算前缀和
// 下标是分数，值是“有多少人不超过这个分数 <=”
for (let i = 1; i < prefix.length; i++) {
prefix[i] += prefix[i - 1];
}
// 第 mi 个同学的分数
const score = scores[mi - 1];
const p = (prefix[score] / scores.length) * 100;
return p.toFixed(6) + '%';
};const __main__ = function () {
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
console.log('******输入******');
rl.prompt();
const inputs = [];
rl.on('line', line => inputs.push(line));
rl.on('close', () => {
const [n, m] = inputs[0].split(' '); // n 个同学， m 次询问
const scores = inputs[1].split(' ').slice(0, n); // 全班同学的分数
const asks = inputs[2].split(' ').slice(0, m); // 每次询问的是第几位同学
console.log('\n******输出******');
asks.forEach(mi => {
const p = test(scores, mi);
console.log(p);
});
});
};