蓝桥P2143：最少刷题数

问题描述

小蓝老师教的编程课有 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.

运行限制

最大运行时间：1s

最大运行内存：512M

解题思路

基本的一个思路就是，对已有的刷题量数据进行排序，找出比它大和比它小的数据的个数，如果不满足题意条件（即不满足“大于它的数据个数比小于它的数据个数少或相等”），就计算它和中位数的差值表示需要再刷的题量，但如果中位数本身不满足题意条件，则再刷的题量需要比中位数还大也就是至少需要再加一。

参考代码

#include <bits/stdc++.h>
using namespace std;

// 定义结构体
typedef struct{
    int no;            // 编号
    int pro,less;      // 已刷题数和还需刷题数
    int left,right;    // 比它小的大的数据个数
} student;

// 按照已刷题数的排序规则
bool comp1(const student &a, const student &b){
    return a.pro<b.pro;
}

// 按照编号的排序规则
bool comp2(const student &a, const student &b){
    return a.no<b.no;
}

int main(){
    int n;
    student a[100000];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i].pro;
        a[i].no=i+1;
        a[i].less=0;
    }

    // 按照已刷题数进行排序
    sort(a,a+n,comp1);
    
    // 采用倒序循环可以先求出中位数的相关值
    for(int i=n-1;i>=0;i--){
        a[i].left=i;
        a[i].right=n-i-1;

        // 计算刷题数小于它的数据个数
        for(int j=i-1;j>=0;j--){
            if(a[j].pro<a[i].pro)
                break;
            a[i].left--;
        }

        // 计算刷题数大于它的数据个数
        for(int j=i+1;j<n;j++){
            if(a[j].pro>a[i].pro)
                break;
            a[i].right--;
        }

        // 如果需要再刷题才能满足条件则计算
        if(a[i].left<a[i].right){
            a[i].less=a[n/2].pro-a[i].pro;

            // 如果中位数本身不满足条件则要比中位数大
            if(a[n/2].left<=a[n/2].right){
                a[i].less=a[i].less+1;
            }
        }
    }

    // 按照学生编号进行排序
    sort(a,a+n,comp2);
    
    for(int i=0;i<n;i++){
        cout<<a[i].less<<" ";
    }
    
    return 0;
}