蓝桥杯2022年第十三届省赛真题-最少刷题数

题目描述
小蓝教的编程课有 N 名学生，编号依次是 1 . . . N。第 i 号学生这学期刷题的数量是 Ai。

对于每一名学生，请你计算他至少还要再刷多少道题，才能使得全班刷题比他多的学生数不超过刷题比他少的学生数。

输入格式
第一行包含一个正整数 N。

第二行包含 N 个整数

输出格式
输出 N 个整数，依次表示第 1 . . . N 号学生分别至少还要再刷多少道题。
样例输入
5
12 10 15 20 6
样例输出
0 3 0 0 7
提示
对于 30% 的数据，1 ≤ N ≤ 1000, 0 ≤ Ai ≤ 1000.

对于 100% 的数据，1 ≤ N ≤ 100000, 0 ≤ Ai ≤ 100000.

我的代码：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int []num=new int[N];
        for(int i=0;i<N;i++) {
            num[i] = sc.nextInt();
        }
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<N;i++){
            map.put(i,num[i]);
        }
        List<Integer> value=new ArrayList<>();
        for (int i=0;i<N;i++){
            value.add(map.get(i));
        }
        Collections.sort(value);
        int []count=new int[N];
        int j=0;
        for(int x:value){
            count[j]=x;
            j++;
        }
        int middle=count[N/2];
        for(int i=0;i<N;i++){
        if(map.get(i)<middle&&N%2!=0){
            System.out.print(middle-map.get(i)+1);
            System.out.print(" ");
        }
        else if(map.get(i)<middle&&N%2==0){
            System.out.print(middle-map.get(i));
            System.out.print(" ");
        }
        else{
            System.out.print(0);
            System.out.print(" ");
        }
        }
        sc.close();
    }
}

十个测试点只有三个通过，哪里出错了？

  • python 代码运行效果截屏

    img


    img

  • 加入时间没算的代码
#!/sur/bin/nve python
# coding: utf-8
import time

def is_add(num):
    ''' 判定还需刷题量 '''
    up = [i for i in stu if i > num] # 解析比当前学生多的刷题量。
    up.sort() # 刷题量多的列表排升序。
    low = [i for i in stu if i < num] # 解析比当前学生少的刷题量。
    result = [] # 当前学生还需刷题量列表初值。
    
    def count(num):
        ''' 递归计算 '''
    
        if (len(up) - len(low)) > 0: # 比当前学生刷题量多、少人数差大于0，递归计算还需刷题量。
            tem = up.pop(0) # 抽取比当前学生刷题量多且最接近的刷题量。
            result2 = tem + 1 - num # 两人刷题量差值+1即是还需刷题量，就会会超过该名学生。
            result.append(result2) # 将还需刷题量计入列表。
            low.append(tem + result2) # 比当前学生刷题量少的人数 +1。
            return count(num + result2) # 递归函数调用，继续计算。

    count(num) # 调用函数计算还需刷题量。
    return sum(result) if result else 0 # 如果有递归计算，则返回计算值；否则返回0。

if __name__ == '__main__':
    start = time.time()
    in_s = '''5
12 10 15 20 6'''
    n = int(in_s.split('\n')[0])
    stu = list(map(int, in_s.split('\n')[1].split()))
    print(f"\n输入：\n{in_s}\n\n预期输出：0 3 0 0 7\n\n实际输出：{' '.join(map(str, [is_add(i) for i in stu]))}") # 用列表解析式解析每个学生还需刷题量，用jion()方法拼接输出。

    #for i in stu:
        #print(i, is_add(i)) # 循环遍历轮询写法。

    print(f"程序用时：{time.time()-start} 秒")

  (我仅会点python ，不懂Java语法，读不太明白Java代码。)只能用python 代码阐述“算法逻辑”。我用递归计算，初达预期，代码冗余，贴出是代码优化后的python 代码。每条语句都注释了，应该可以看出“算法逻辑”。算法不限语言，自由不分国界。

  • python 代码运行效果截屏图片

    img

  • python 代码(优化后)

#!/sur/bin/nve python
# coding: utf-8


def is_add(num):
    ''' 判定还需刷题量 '''
    up = [i for i in stu if i > num] # 解析比当前学生多的刷题量。
    up.sort() # 刷题量多的列表排升序。
    low = [i for i in stu if i < num] # 解析比当前学生少的刷题量。
    result = [] # 当前学生还需刷题量列表初值。
    
    def count(num):
        ''' 递归计算 '''
    
        if (len(up) - len(low)) > 0: # 比当前学生刷题量多、少人数差大于0，递归计算还需刷题量。
            tem = up.pop(0) # 抽取比当前学生刷题量多且最接近的刷题量。
            result2 = tem + 1 - num # 两人刷题量差值+1即是还需刷题量，就会会超过该名学生。
            result.append(result2) # 将还需刷题量计入列表。
            low.append(tem + result2) # 比当前学生刷题量少的人数 +1。
            return count(num + result2) # 递归函数调用，继续计算。

    count(num) # 调用函数计算还需刷题量。
    return sum(result) if result else 0 # 如果有递归计算，则返回计算值；否则返回0。

if __name__ == '__main__':
    in_s = '''5
12 10 15 20 6'''
    n = int(in_s.split('\n')[0])
    stu = list(map(int, in_s.split('\n')[1].split()))
    print(f"\n输入：\n{in_s}\n\n预期输出：0 3 0 0 7\n\n实际输出：{' '.join(map(str, [is_add(i) for i in stu]))}") # 用列表解析式解析每个学生还需刷题量，用jion()方法拼接输出。

    '''for i in stu:
        print(i, is_add(i))''' # 循环遍历轮询写法。