fantacy

用户名：dotcpp0750464

访问量：177

签　名：

等　　级
排　　名	29065
经　　验	522
参赛次数	0
文章发表	2
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

左移右移双向链表 c++
浏览：70

你可能喜欢

C语言训练-求1+2!+3!+...+N!的和（C++代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

最少刷题数 c++

　　作者: fantacy　　　　发表时间：2024-04-08 10:59:59 浏览：88　|　评论：0　

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

#### 思路
1. 数组排序，求中位数的**下标**mid，mid必须满足mid左边数的个数要大于等于mid右边数的个数
2. 对于每一个ai，设修改后的ai为nx，依照题意，需要求最小的nx
3. 可以考虑nx与数组中位数的关系，若nx在中位数的右边，则比nx小的数一定大于等于比nx大的数
    - ai > b[mid] 则已经符合题意，res = 0
    - ai == b[mid]，则需要考虑数组中严格小于mid的数的个数l，以及严格大于mid数的个数r
        - 若l >=r 则ai可以取到 mid，res = 0
        - 若l < r 则ai至少取到 mid+1, res = 1
    - ai < mid, 同等于的情况分析，看ai能否取到mid，但是需要注意，ai改变后，l的个数会减一，判断的时候注意即可

#### 时间复杂度
O(n + log(n))

#### 示例代码
```
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N], b[N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    // 求中中位数的下标，对于偶数个序列，取前一段较长的数 例：1 5 6 10 取中位数 6
    int mid = n / 2 + 1, l = 0, r = 0;
    
    // 求中位数的左边比中位数的小的数
    int ll = 1, rr = mid;
    while(ll < rr)
    {
        int tmp = ll + rr + 1 >> 1;
        if(b[tmp] < b[mid]) ll = tmp;
        else rr = tmp - 1;
    }
    if(b[ll] < b[mid]) l = ll;
    
    // 求中位数的右边比中位数的大的数
    ll = mid, rr = n;
    while(ll < rr)
    {
        int tmp = ll + rr >> 1;
        if(b[tmp] > b[mid]) rr = tmp;
        else ll = tmp + 1;
    }
    if(b[ll] > b[mid]) r = n - ll + 1;
    
    // 遍历每一个ai
    for(int i = 1; i <= n; i++)
    {
        int t = 0;
        if(a[i] == b[mid])
        {
        	if(l < r) t = b[mid] + 1 - a[i];
		}
        else if(a[i] < b[mid])
        {
            if(l - 1 >= r) t = b[mid] - a[i];
            else t =  b[mid] + 1 - a[i];
        }
        printf("%d ", t);
    }
    
    return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

fantacy

TA的其他文章

你可能喜欢

人民币问题（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C++代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

最少刷题数 c++

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）for循环

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

淘淘的名单（C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

简单的a+b （C语言代码）

统计立方数（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

【回文数(二)】（C语言代码）

A+B for Input-Output Practice (I) （C++代码）

Manchester-字符串的输入输出处理

fantacy

TA的其他文章

你可能喜欢

人民币问题 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C++代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

最少刷题数 c++

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）for循环

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

淘淘的名单 （C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

简单的a+b （C语言代码）

统计立方数 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

【回文数(二)】 （C语言代码）

A+B for Input-Output Practice (I) （C++代码）

Manchester-字符串的输入输出处理

人民币问题（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C++代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

　　评论区

淘淘的名单（C语言代码）

统计立方数（C语言代码）

【回文数(二)】（C语言代码）