首页 > 试题广场 >

小易的英语软件

[编程题]小易的英语软件

热度指数：3215 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小易是班级的英语课代表, 他开发了一款软件开处理他的工作。
小易的软件有一个神奇的功能，能够通过一个百分数来反应你的成绩在班上的位置。“成绩超过班级 ...% 的同学”。
设这个百分数为 p，考了 s 分，则可以通过以下式子计算得出 p：
p = ( 分数不超过 s 的人数 - 1) $\div$ 班级总人数 $\times 100\%$
突然一天的英语考试之后，软件突然罢工了，这可忙坏了小易。成绩输入这些对于字写得又快又好的小易当然没有问题，但是计算这些百分数……这庞大的数据量吓坏了他。
于是他来找到你，希望他编一个程序模拟这个软件：给出班级人数 n，以及每个人的成绩，请求出某几位同学的百分数。

输入描述:

第一行一个整数 n，表示班级人数。 
第二行共 n 个自然数，第 i 个数表示第 i 位同学的成绩 。 
第三行一个整数 q，表示询问的次数。 
接下来 q 行，每行一个数 x，表示询问第 x 位同学的百分数。

输出描述:

输出应有 q 行，每行一个百分数，对应每一次的询问。

为了方便，不需要输出百分号，只需要输出百分号前的数字即可。四舍五入保留六位小数即可。

示例1

输入

输出

66.666667
33.333333
0.000000

算法知识视频讲解

dragonlogin

思路

发现分数最大值是150，题目要求每次找不超过分数x的人数，需要找10000次。

考虑暴力解法
每次找不超过分数x的人数，都遍历一次数组，需要遍历10000次，肯定超时
优化
优化可以优先考虑空间换时间，所以可以用map存每个分数的人数，然后遍历分数就可以了，最多只需要遍历150次

#include <bits/stdc++.h>
using namespace std;
const int N = 10010, M = 160;
int a[N], mp[M];
int n, q;
int main() {
    scanf("%d", &n);
    memset(mp, 0, sizeof mp);
    for (int i = 1; i <= n; ++ i) {
        scanf("%d", &a[i]);
        mp[a[i]] ++ ;
    }
    scanf("%d", &q);
    int x;
    while (q -- ) {
        scanf("%d", &x);
        int cnt = 0;
        for (int i = 0; i <= a[x]; ++ i) {
            cnt += mp[i] ;
        }
        // 必须用double，用float 错误
        double ret = (cnt - 1) * 100.0 / n ;
        printf("%.6lf\n", ret);
    }

    return 0;
}

发表于 2020-07-30 18:17:51 回复(0)

牛客717970517号

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
	vector<int>scores;
	int n;  //班级人数
	cin >> n;
	int* a = new int[n];
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];        //每个学生的分数
	}
	int q;   //询问的次数
	cin >> q;
	for (int i = 0; i < q; i++)
	{
		int bianhao;
		cin >> bianhao;      //询问的是哪个学生
		scores.push_back(a[bianhao-1]);       //q个学生的成绩放入vector中
	}
	sort(a, a + n);
	for (int i = 0; i < q; i++)
	{
		for (int j = n - 1; j >= 0; j--)
		{
			if (a[j] == scores[i])
			{

				double percent = j*100.0 / n;
				printf("%.6lf\n", percent);
				break;
			}
		}
	}
}

发表于 2020-08-07 15:47:08 回复(0)

悦兮

思路：排序成绩数组，之后通过二分查找找到成绩在数组中的位置，即可知道有多少同学的分数低于他/她。

排序和二分查找的时间复杂度均为O(n log(n))。

import bisect

n = int(input())
scores = list(map(int, input().split()))
sort = sorted(scores)
q = int(input())
for _ in range(q):
    idx = int(input()) - 1
    rank = bisect.bisect(sort, scores[idx]) - 1
    print('{:.6f}'.format(rank * 100 / n))

计数

思路：类似于计数排序，因为成绩是有范围的0 - 150，创建一个合适范围的数组，统计每个分数下有多少学生。之后通过累积和计算出小于该分数的学生数。

统计的时间复杂度为O(n)。

空间复杂度为O(1)。无论多少学生，总是需要一个长度为(最大分数 + 1)的分数数组。

n = int(input())
scores = list(map(int, input().split()))
q = int(input())

counter = [0] * 151
for s in scores:
    counter[s] += 1
# 统计分数小于等于 i 的人数，存储在 counter[i] 中
for i in range(1, len(counter)):
    counter[i] += counter[i - 1]

for _ in range(q):
    x = int(input())
    s = scores[x - 1]  # 第 x 位同学的分数
    print('{:.6f}'.format((counter[s] - 1) * 100 / n))

编辑于 2020-08-04 10:57:43 回复(0)

ADPX丶

import java.util.Scanner;
 
public class Main{
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        int query = sc.nextInt();
        for (int i = 0; i < query; i++) {
            int index = sc.nextInt();
            double ans = moreThan(nums,index) * 1.0 / n * 100;
            System.out.printf("%.6f",ans);
            System.out.println();
        }
    }
 
 
    public static int moreThan(int[] nums, int i){
 
        int point = nums[i - 1];
        int count = 0;
        for (int j = 0; j < nums.length; j++) {
            if(nums[j] <= point) ++count;
        }
        return --count;
    }
}

发表于 2020-04-13 17:53:14 回复(0)

牛客252866651号

#include<iostream>
using namespace std;

int main() {
	double n;//班级人数
	double a[10002];
	int q;//询问的次数
	double x;

	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	cin >> q;
	int m;
	double y = 0;

	for (int i = 0; i < q; i++) {
		cin >> m;
		for (int k = 1; k < n + 1; k++) {
			if (a[m] >= a[k])
				y++;
		}
		x = (y - 1) / n * 100;
		printf("%0.6lf\n", x);
		y = 0;
	}
	return 0;
}

发表于 2020-04-09 21:20:12 回复(0)

ButterBeer

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int len = sc.nextInt();
            int[] scores = new int[len];
            for (int i=0;i<len;i++){
                scores[i] = sc.nextInt();
            }
            HashMap<Integer,Integer> scoreMap = main.creatHashmap(scores,len);
            int queryLen = sc.nextInt();
            for (int i = 0;i<queryLen;i++){
                System.out.printf("%.6f\n",main.outputRank(scoreMap,scores,len,sc.nextInt()-1));
            }
        }
    }

    public HashMap<Integer,Integer> creatHashmap(int[] scores,int len){
        int[] copy = Arrays.copyOf(scores,len);
        Arrays.sort(copy);
        HashMap<Integer,Integer> hashpmap = new HashMap<>();
        int count = 0;
        for (int i=0;i<len;i++){
            if (hashpmap.containsKey(copy[i])){
                hashpmap.put(copy[i],hashpmap.get(copy[i])+1);
                count++;
            }
            else{
                count++;
                hashpmap.put(copy[i],count);
            }
        }
        return hashpmap;
    }

    public Double outputRank(HashMap<Integer,Integer> hashMap,int[] scores,int len,int query){
        double ans=0;
        double rank = hashMap.get(scores[query]);
        ans = (rank-1)*100/len;
        return ans;
    }
}

题目本身不难，但是调了好久的精度终于AC了

发表于 2020-04-01 16:52:11 回复(1)

Muche

前缀和即可，查询时就是O（1）复杂度

 import java.util.*;


public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] stu = new int[n];
        int[] grade = new int[151];
        int[] profix = new int[152];
        for (int i = 0; i < n; i++) {
            stu[i] = in.nextInt();
            grade[stu[i]]++;
        }
        profix[0] = grade[0];
        for (int i = 1; i <= 150; i++) {
            profix[i] = profix[i - 1] + grade[i];
        }
        int q = in.nextInt();
        for (int i = 0; i < q; i++) {
            int idx = in.nextInt();
            double x = (profix[stu[idx - 1]] - 1) / (double)n;
            System.out.println(String.format("%.6f", x * 100));
        }
    }

}

编辑于 2020-08-08 16:57:59 回复(0)

chenjiag

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 输入同学数
        int n = in.nextInt();
        in.nextLine();
        int[] scores = new int[n];
        Map<Integer, Integer> map = new HashMap<>();
        Map<Integer, Double> res = new HashMap<>();
        for (int i = 0; i < n; i++) {
            scores[i] = in.nextInt();
            map.put(i, scores[i]);
        }
        Arrays.sort(scores);
        for (int i = 0; i < n; i++) {
            res.put(scores[i], ((double)i / n) * 100);
        }
        // 查询组数
        int q = in.nextInt();
        in.nextLine();
        while (q-- > 0) {
            int x = in.nextInt();
            double d = res.get(map.get(x - 1));
            System.out.println(String.format("%.6f", d));
        }
    }
}

发表于 2021-05-25 20:23:18 回复(0)

牛客339216640号

查询成绩时暴力方法，结果可以成功提交，显示未超时。代码可以优化。

通过一个函数调用来解决问题，本身问题不难，注意结果需要输出6位小数，采用double类型处理

#include<iostream>

#include<vector>
using namespace std;

// 计算第num个的成绩
void f(vector<int>score, int n, int num){
int cnt = 0;
for (int i = 0; i<n; i++)
if (score[i] <= score[num])
cnt++;
double ret=(cnt-1)*100.0/n;
printf("%6f", ret);
cout << endl;
}

int main(){
int n, q; // 班级人数,查询次数
//cout<<"请输入班级人数 n=";
cin >> n;
vector<int> score(n); //表示每个人的成绩
//cout<<"请输入每个人的成绩";
for (int i = 0; i<n; i++)
cin >> score[i];
//cout<<"请输入查询次数 q=";
cin >> q;
vector<int> num(q);
// cout<<"请输入查询编号 num=";
for (int i = 0; i<q; i++)
cin >> num[i];
//cout << "输出查询" << q << "次的成绩" << endl;
for (int i = 0; i<q; i++)
f(score, n, num[i]-1); // 计算查询q次的成绩
return 0;
}

发表于 2020-08-07 22:11:21 回复(0)

scutlwy

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int stuNum = Integer.parseInt(in.nextLine());
        int[] score = new int[stuNum];
        for(int i = 0;i<stuNum; i++){
            score[i] = in.nextInt();
        }
        int[] rank = Arrays.copyOf(score,stuNum);
        Arrays.sort(rank);
        int[] dp = new int[151];
        for(int i = 0;i<stuNum; i++){
            dp[rank[i]] = i;
        }
        int queryNum = in.nextInt();
        for(int i=0;i<queryNum; i++){
            int stu = in.nextInt();
            int grade = score[stu-1];
            double res = dp[grade]*1.0/stuNum * 100;
            System.out.printf("%.6f\n", res);
        }
    }
}

发表于 2020-08-07 21:05:06 回复(0)

TinySu

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        //输入数据
        int n = input.nextInt();
        short[] a = new short[n];
        for(int j = 0; j < n; j++){
        	a[j] = input.nextShort();
    	} 

        //输入数据
        int q = input.nextInt();
        int[] x = new int[q];
        for(int j = 0; j < q; j++){
        	x[j] = input.nextInt();
    	} 

        //创建副本并排序
        short[] temp = Arrays.copyOf(a, n);
        Arrays.sort(temp);

        //index既是下标索引，又是不大于分数x的总人数
        for(int j = 0; j < q; j++){
        	int index = Arrays.binarySearch(temp, a[x[j] - 1]);
        	for(; index < n; index++) {
        		if(temp[index] > a[x[j] - 1])
        			break;
        	}
        	
        	double count = index - 1;
        	double res = count / n * 100;
        	System.out.printf("%.6f\n", res);
    	}
        
    }
    
   
}

发表于 2020-08-07 00:40:06 回复(0)

offer该回家了吧

package com.example.demo.test.neteasy;

import java.math.BigDecimal;
import java.text.DecimalFormat;
import java.util.HashMap;
import java.util.Scanner;

public class T1 {
    private static int[] score=new int[10001];
    private static int[] sortArr=new int[10001];
    private static int[] query=new int[10001];
    private static HashMap<Integer,Integer> map=new HashMap<>();
    private static int n=0;//学生总数
    private static int m=0;//询问总数


    public static void getRank(){
        sort();
        double t=0;
        double ans;
        for(int i=0;i<m;i++){
            t=map.get(score[query[i]-1]);
            ans=100*(n-t)/n;
            DecimalFormat df = new DecimalFormat("#0.000000");
            String str = df.format(ans);
            System.out.println(str);
        }
    }



    public static void sort(){

        for(int i=0;i<n;i++){
            for(int j=0;j<n-1;j++){
                if(sortArr[j]<sortArr[j+1]){
                    swap(j,j+1);
                }
            }
        }

        for(int i=0;i<n;i++){
            // 一开始没看清题目没 A过 吐了 少了个if判断
            if(!map.containsKey(sortArr[i])){
                map.put(sortArr[i],i+1);
            }
        }
        //System.out.println();
    }

    public static void swap(int i,int j){
        int t=sortArr[i];
        sortArr[i]=sortArr[j];
        sortArr[j]=t;
    }


    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        for(int i=0;i<n;i++){
            score[i]=scanner.nextInt();
            sortArr[i]=score[i];
        }
        m=scanner.nextInt();
        for(int i=0;i<m;i++){
            query[i]=scanner.nextInt();
        }
        getRank();

    }
}

发表于 2020-08-04 23:10:14 回复(0)

7845

哪位大佬能帮忙看看为啥会出现请检查是否存在数组越界等非法访问情况
case通过率为0.00%的报错，测试用例都是通过的。

import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc= new Scanner(System.in);
        int n= sc.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        int q=sc.nextInt();
        int[] x=new int[q];
        for(int i= 0;i<q;i++){
            x[i]=sc.nextInt();
        }
        int[] count=new int[n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(a[i]>a[j]){
                    count[i]++;
                }
             }
          }
      
        for(int i=0;i<q;i++){
            double m=(double) count[i]/n*100;

            System.out.printf("6.f%",m);
        }
    }
}

发表于 2020-08-03 21:26:07 回复(0)

Python

瓜子二手车内推

n = int(input())
score = str(input()).split()
score = [int(xi) for xi in score]
cou = int(input())
l = []
for i in range(cou):
l.append(int(input()))
score_sort = sorted(score)
for j in l:
s = score[j-1]
num = score_sort.index(s)
for i in range(num+1, n):
if score_sort[i] == s:
num += 1
else:
break
tmp = 100*num/n
print('%0.6f'%tmp)

发表于 2020-07-17 16:16:24 回复(1)

kelly逸狼居

对n个数排序后进行统计，注意相同分数的处理

发表于 2020-05-16 12:33:40 回复(0)

Zoe-zyy

from fileinput import input
args = []
for line in input():
    if line:
        args.append(list(line.split()))
n = args.pop(0)
n = int(n[0])
scores = args.pop(0)
scores = list(map(float, scores))
q = args.pop(0)
q = int(q[0])
 
scores_sort = sorted(scores)
while args:
    x = args.pop(0)
    x = int(x[0]) - 1
    s = scores[x]
    num = scores_sort.index(s)
    for i in range(num+1, n):
        if scores_sort[i] == s:
            num += 1
        else:
            break
    tmp = 100 * num / n
    print('%.6f' % tmp)

编辑于 2020-05-09 21:05:30 回复(0)

Geek123321

importjava.util.*;

publicclassMain {

publicstaticvoidmain(String[] args) {

Scanner scanner =newScanner(System.in);

doublen = scanner.nextFloat();

int[] a =newint[(int)n];

for(inti=0;i<n;i++){

a[i] = scanner.nextInt();

}

intq = scanner.nextInt();

int[] b =newint[q];

for(inti=0;i<q;i++){

b[i] = scanner.nextInt();

}

for(inti=0;i<q;i++){

doubletemp = (num(a,b[i])-1)/n*100;

System.out.printf("%.6f\n",temp);

}

publicstaticdoublenum(int[] a,inti){

doublecount=0;

for(intj=0;j<a.length;j++){

if(a[j]<=a[i-1]){count++;}

}

returncount;

}

发表于 2020-04-07 17:35:01 回复(0)

Java

WhyVent

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nArrays = new int[n];
        for(int i=0;i<n;i++){
            nArrays[i] = scanner.nextInt();
        }
        int q = scanner.nextInt();
        int count = 0;
        for(int i=0;i<q;i++){
            int qArray = nArrays[scanner.nextInt()-1];
            for(int j=0;j<n;j++){
                if(nArrays[j]<=qArray){
                    count++;
                }
            }
            System.out.println(String.format("%.6f",(count-1)*100.0/n));
            count = 0;
        }
    }
}

发表于 2020-04-07 12:17:56 回复(0)

永远……

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double n = sc.nextDouble();//班级人数n
        int [] scores = new int[(int)n];//分数数组
        for (int i = 0; i < (int)n; i++) {
            scores[i] = sc.nextInt();
        }
 
        int q = sc.nextInt();//表示询问的次数
        for (int j = 0; j < q; j++) {
            int x = sc.nextInt();
            int s = num(scores[x-1],scores);
            System.out.println(String.format("%.6f",((s-1)/n)*100));//保留6位小数 四舍五入
        }
    }
 
    public static int num(int score,int[] scores){
        int k = 0;
        for (int i : scores) {
            if(score >= i){
                k++;
            }
        }
        return k;
    }
}

发表于 2020-04-05 18:41:25 回复(0)

cyu21

比较简单。直接遍历成绩数组，把小于等于目标成绩的人数记录后便可求解。

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int n = scanner.nextInt();
            int[] a = new int[n];
            int sum = 0;
            for (int i = 0; i < a.length; i++) {
                a[i] = scanner.nextInt();
                sum += a[i];
            }
            int q = scanner.nextInt();
            int[] x = new int[q];
            for (int i = 0; i < x.length; i++) {
                x[i] = scanner.nextInt();
            }
 
            for (int value : x) {
                int s = a[value-1];
                int total = 0;
                for (int i : a) {
                    if (i <= s) {
                        total++;
                    }
                }
                double p = (double)(total-1)/n;
                System.out.printf("%.6f\n",p*100);
                 
            }
        }
 
    }
}

编辑于 2020-04-04 21:06:12 回复(0)