题目描述

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

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

输入格式

第一行包含一个正整数 N。

第二行包含 N 个整数：A1, A2, A3, . . . , AN.

输出格式

输出 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.

思路1

  1. 键盘录入n，然后遍历录入长度为n的数组
  2. 利用循环，判断全班比第i个刷的多以及刷的少的数目
  3. 根据多和少的数目进行判断，对a【i】进行++，直到符合条件输出

代码1

import java.util.Scanner;

public class Lanqiao2673 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        //N名学生
        int n=sc.nextInt();
        //遍历输入
        int[] a =new int[n];
        for (int i = 0; i< a.length ; i++)
        {
             a[i]=sc.nextInt();
        }
      
        for (int i = 0; i < a.length; i++) {
            int sum=0;
            int s=0;
            int d=0;
            //临时变量记录a【i】的初始值
            int temp=a[i];
            //循环判断第i个比他多及比他少的数
            for (int j = 0; j < a.length; j++) {
                if (a[i] > a[j]) s++;
                if (a[i] < a[j]) d++;
            }
            //根据多与少的关系判断是否需要++，并记录++的次数
            while(d>s){
                a[i]++;
                sum++;
                s=0;
                d=0;
                for (int j = 0; j < a.length; j++) {
                    if (a[i] > a[j]) s++;
                    if (a[i] < a[j]) d++;
                }
            }
            a[i]=temp;
            System.out.print(sum+" ");
        }

    }

}

结果可正确执行，但是放入oj平台发现超时

pCgU9Yj.png

改进：思路2

1.先创一个数组b（复制数组a），然后对数组b排序。

2.然后求出中间值u的个数、比中间值大的个数d、比中间值小的个数s，然后开始遍历数组a，下标从0开始，即0~(n-1)，然后每次根据数组a找出对应的在数组b中的位置pos

3.然后开始判断****b[pos]与u****之间的关系

**b[pos] > u*

不需要任何条件就能满足

**b[pos] == u*

如果d <= s的话，则你不刷题也能满足条件，即目标题数为u题,就不用加了，直接输出0

反之，则说明这些人需要再刷1题，即目标题数为u + 1题，就需要输出1

**b[pos] < u*

我们先将b[pos]加到u，我们会知道此时s就会减1，而d不变（因为b[pos]此时跟u相等了），所以如果此时d <= s - 1 ,满足条件，就只需要加到u即可，即结果为u - a[i]

反之，这些人的题数必须定为u + 1题

代码2

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

public class Lanqiao2673new {
        static int N = 100010;
        static int[] a = new int[N];
        static int[] b = new int[N];
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            for(int i = 0; i < n;i++) {
                a[i] = sc.nextInt();
                b[i] = a[i];
            }
            Arrays.sort(b,0,n);
//        求出中间值
            int u = b[n / 2];
            boolean flag = false;
//        求出比u大的个数和比u小的个数

            int s = 0,d = 0;
//        求出u的个数
            int Unum = 0;
            for(int i = 0; i < n;i++) {
                if(b[i] == u) {
                    Unum++;
                    if(!flag) {
                        s = i;
                        flag = true;
                    }
                }
            }
            d = n - Unum - s;
//        判断与u相同的数
            for(int i = 0; i < n;i++) {
                int pos = Arrays.binarySearch(b,0,n, a[i]);
//            如果找的值不是中间值
                if(b[pos] < u) {
                    //如果右边小于左边减1
                    if(d <= s - 1) {
                        System.out.print(u - a[i] + " ");
                    }else {
                        System.out.print(u + 1 - a[i] + " ");
                    }
                }else if(b[pos] > u) {
                    System.out.print(0 + " ");
                }else {
                    if(d <= s) System.out.print(0 + " ");
                    else System.out.print(1 + " ");
                }
            }
        }
    }