电子科技大学链时代工作室招新题C语言部分---题号D

1. 题目

这道题大概的意思就是对一个整形数组的元素进行排序,然后按新的顺序打印原本的下标;

例如,在题目给出的Note部分,{a1, a2, a3, a4, a5}进行排序之后变为了{a2, a1, a4, a3, a5},于是输出2 1 4 3 5。

排序的规则是,排完序之后,使得新数组与原数组的每个对应位置上的元素相加之后,的到一个相同的数;

例如,在题目给出的Note部分,a1 + a2 = 6,a2 + a3 = 6,……

输入

第一行输入数组的元素个数,第二行输入数组的内容

输出

依次输出新数组的原下标,如果无法找到这样一个新的排列顺序,就输出-1。


2. 第一版解法

第一版是暴力解法,直接对题意进行翻译,结果也是不出意外地超时了。

2.1 思路

1. 首先假设第一个元素与第i个元素配对,并将它们的和存在一个变量sum中。

2. 然后依次检查之后的元素是否能找到另一个元素与其相加,得到的和恰好等于sum。

3. 如果某个元素找不到与其相对应的元素,就使第一个元素与i+1个元素配对,并重新检查。

4. 若检查到最后,每一个元素都无法和第一个元素配对,则表示无法找到符合题意的排序,打印-1并退出。

5. 如果第一个元素与某个元素配对时,每一个元素都能找到与自己相配对的元素,则按顺序打印与原数组相配对的元素的下标。

2.2 代码

#include <stdio.h>
#include <stdlib.h>

void sort(int n, int arr[])
{
    int i = 0;
    for(i = 0; i < n; i++)//arr[0]和arr[i]对应
    {
        int x = 1;
        int* ret = (int*)malloc(sizeof(int) * n);
        int* test = (int*)malloc(sizeof(int) * n);
        for(int h = 0; h < n; h++)
        {
            test[h] = 1;
        }
        ret[0] = i;
        test[i] = 0;
        int tmp = arr[0] + arr[i];
        int j = 1;
        for(j = 1; j < n; j++)//后面元素找对应
        {
            int flag = 1;
            for(int k = 0; k < n; k++)
            {
                if((tmp == arr[j] + arr[k])&&test[k] != 0)//找到对应元素
                {
                    flag = 0;
                    test[k] = 0;
                    ret[x] = k;
                    x++;
                    break;
                }
            }
            if(flag)//某号元素找不到对应
            break;
        }
        if(j == n)//找全了
        {
            for(int y = 0; y < n; y++)
            {
                printf("%d ", ret[y]+1);
            }
            break;
        }
        free(ret);
        free(test);
    }
    if(i == n)
    printf("-1\n");
}

int main()
{
    int n = 0, k = 0;
    k = scanf("%d", &n);
    int* arr = (int*)malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++)
    {
        k = scanf("%d", &arr[i]);
    }
    sort(n, arr);
    free(arr);
    return 0;
}

2.3 总结

这一版解法缺乏对题目的深入分析,以及对数学关系的挖掘。

由此导致程序做了很多不必要的计算,使得时间复杂度过高而超时。


3. 第二版解法

这一版尝试减小时间复杂度。

3.1 挖掘数学关系,优化算法

3.1.1 有关sum

1. sum是每组元素相加之和,我们仔细分析就会发现,sum其实是平均数的二倍,于是我们无需再尝试第一个元素该与谁配对。

2. 其次,sum是两个整形之和,它也必定为整数,所以我们将sum定义为浮点数,并检验“sum == (int)sum”是否成立,如果不成立则直接输出-1。这样,某些不能找到结果的样例就可以直接判断为不符合要求,而不需要找到最后再做出判断;

例如数组{1, 2, 3, 7},其平均数的二倍为6.5,一定不能找到合适的结果。

3.1.2 有关配对

如果第1号元素与第5号元素配对了,那么我们就不必再去寻找第5号元素该与第几号元素配对,直接使其与1号元素配对即可;

例如题上第一个案例{4, 2, 5, 1, 3},打印的结果为2 1 4 3 5

结果的第一个位置上是2,第二个位置上是1

           第三个位置上是4,第四个位置上是3

           第五个位置上是5。

这样就可以为我们的循环减少一半的工作量。

3.2 代码

#include <stdio.h>
#include <stdlib.h>

void solve(int n, int arr[])
{
    double sum = 0;
    for(int j = 0; j < n; j++)
    {
        sum += (double)arr[j];
    }
    sum = sum*2/n;
    if(sum == (int)sum)
    {
        int i = 0;
        int ret[n];
        for(int j = 0; j < n; j++)
        {
            ret[j] = 0;
        }
        for(i = 0; i < n; i++)
        {
            if(ret[i] != 0)
            continue;
            int flag = 1;
            for(int j = 0; j < n; j++)
            {
                if(ret[j] != 0)
                continue;
                if(arr[i] + arr[j] == sum)
                {
                    flag = 0;
                    ret[i] = j + 1;
                    ret[j] = i + 1;
                    break;
                }
            }
            if(flag)
            {
                printf("%d\n", -1);
                return;
            }
        }
        if(i == n)
        for(int k = 0; k < n; k++)
        printf("%d ", ret[k]);
        printf("\n");
    }
    else
    printf("%d\n", -1);
}

int main()
{
    int n = 0, k = 0;
    k = scanf("%d", &n);
    int* arr = (int*)malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++)
    {
        k = scanf("%d", &arr[i]);
    }
    solve(n, arr);
    free(arr);
    return 0;
}

3.3 总结

这次深入分析了题目中的数学关系,并对算法做了大量的优化。

但是仍然超时,能反应的过来吗牢底?我当时血压都高了。

但是没办法,我们只能继续做优化。


4. 最终版本

算法已经够简单了,优化一下思路。

4.1 换个思路

就刚才的思路而言,我们必须要用到二重循环,尽管我们已经将二重循环的工作量减少了一半,但仍然超时。那么就说明,一定有更好的算法,使得时间复杂度能降到O(n)

4.1.1 排序的思路

经过上一版的启发,我们发现,最大的数一定和最小的数配对,第二小的数一定和第二大的数配对……

于是,我们想到先将数组进行排序,这样就不必再费力再用二重循环去找配对的元素了。

可是,有两个问题(这也是我一开始没有采用这种思路的原因):

1. 排序的实现,仍然需要二重循环(博主比较菜,还只会冒泡排序)。

2. 排序之后如何知道每个元素原来的下标。

对于第一个问题,我们可以只用qsort函数来帮助我们实现排序,因为其采用的是一种快速排序的方法。

对于第二个问题:

1. 我一开始的想法是将原数组的数据存储到一个结构体数组中,结构体包含两个元素,一个是int类型的数据,一个是该数据对应的下标。让qsort函数按照数据排序,我再访问另一个成员对下标进行配对。

2. 但是,数据本来就是由两部分构成的啊:数据的值与地址。所以我可以将各个元素的地址存放到一个指针数组中,然后让qsort根据其指向的值对地址进行排序,又由地址减去arr的到下标,进行配对。

4.2 代码

#include <stdio.h>
#include <stdlib.h>

int add_cmp(const void* e1, const void* e2)
{
    return **(int**)e1 - **(int**)e2;
}

void solve(int n, int arr[])
{
    double sum = 0;
    for(int j = 0; j < n; j++)
    {
        sum += (double)arr[j];
    }
    sum = sum*2/n;
    if(sum == (int)sum)
    {
        int** add = (int**)malloc(sizeof(int*) * n);
        int* ret = (int*)malloc(sizeof(int) * n);
        for(int i = 0; i < n; i++)
        {
            add[i] = &arr[i];
        }
        qsort(add, n, sizeof(int*), add_cmp);
        for(int i = 0, j = n-1; i <= j; i++, j--)
        {
            if(*add[i] + *add[j] != sum)
            {
                printf("%d\n", -1);
                return;
            }
            else
            {
                int e1 = add[i] - arr;
                int e2 = add[j] - arr;
                ret[e1] = e2 + 1;
                ret[e2] = e1 + 1;
            }
        }
        for(int i = 0; i < n; i++)
        {
            printf("%d ", ret[i]);
        }
        printf("\n");
        free(add);
        free(ret);
    }
    else
    printf("%d\n", -1);
}

int main()
{
    int n = 0, k = 0;
    k = scanf("%d", &n);
    int* arr = (int*)malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++)
    {
        k = scanf("%d", &arr[i]);
    }
    solve(n, arr);
    free(arr);
    return 0;
}

4.3 总结

这次循环最多只有一重了,如果再不过就不太厚道了。那么也是理所当然地拿下第一题。

你问为什么第一题是D?因为前三道是保护自尊心的送分题,小学生都会做,我们就直接跳过。

C语言题的题号一直到H,感兴趣的同学点波关注,我们尽快更新。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/466402.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

MyBatisPlus中MetaObjectHandler的使用

系列文章目录 文章目录 系列文章目录前言前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女通用,看懂了就去分享给你的码吧。 起因是公司一个同事接到需求,让把一条数据录入时createTime字段,设置为…

DM数据库(docker)

docker安装 安装必要的系统工具 yum install -y yum-utils device-mapper-persistent-data lvm2 配置阿里云Docker Yum源: yum-config-manager --add-repo http://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo 更新yum缓存 yum makecache fast 安装docker-CE: y…

抛弃Superhuman?这些替代方案让你眼前一亮!

Superhuman是一个极好的人工智能工具在电子邮件助理领域。根据SimilarWeb的最新统计&#xff0c;它在全球网站排名中排名第21980位&#xff0c;月访问量为1751798。然而市场上还有许多其他优秀的选择。为了帮助您找到最适合您需求的解决方案&#xff0c;我们为您精心挑选了10种…

海淘注意事项,海淘虚拟卡

2024年海淘visa信用卡&#xff0c;点击获取卡片 海淘注意事项 海淘&#xff08;跨境购物&#xff09;可以让人们在国外购买到更多种类的商品&#xff0c;但是也需要注意一些事项&#xff0c;以确保购物的顺利进行和商品的质量。以下是一些建议&#xff1a; 海淘网站的选择&…

零代码编程:用kimichat合并一个文件夹下的多个文件

一个文件夹里面有很多个srt字幕文件&#xff0c;如何借助kimichat来自动批量合并呢&#xff1f; 在kimichat对话框中输入提示词&#xff1a; 你是一个Python编程专家&#xff0c;完成如下的编程任务&#xff1a; 这个文件夹&#xff1a;D:\downloads\life.on.our.planet.(202…

C++中的using关键字

1. 类型别名 using关键字可以用来为类型创建一个新的名字&#xff0c;这在代码的可读性和维护性方面非常有帮助。 // 定义类型别名 using IntPtr int*;// 使用 int value 5; IntPtr ptr &value;2. 命名空间别名 如果你正在使用一个非常长的命名空间&#xff0c;可以使…

如何在MT4平台查询自己的账户杠杆?

如何在MT4平台查询自己的账户杠杆?MT4中直接没有这个选项&#xff0c;犟嘴的投资者千万不要犟嘴&#xff0c;说可以根据保证金水平计算。其实在交易账户中有3中方法可以查询自己的账户&#xff0c;投资者可以在这里开立一个MT4帐户&#xff0c;并将其附加到具有登录名和密码的…

Jenkins-pipeline流水线构建完钉钉通知

添加钉钉机器人 在钉钉群设置里添加机器人拿出Webhook地址&#xff0c;设置关键词 Jenkins安装钉钉插件 Dashboard > 系统管理 > 插件管理&#xff0c;搜索构建通知&#xff0c;直接搜索Ding Talk也行 安装DingTalk插件&#xff0c;重启Jenkins 来到Dashboard > 系…

想要了解更多商品信息?淘宝天猫详情接口API助你一键搞定!

想要了解更多商品信息&#xff1f;淘宝天猫详情接口API是你的理想选择&#xff01;作为唯一提供官方商品数据的接口&#xff0c;它能够帮助你快速获取商品的多种详细信息&#xff0c;联讯数据让你在购物过程中做出更明智的决策。 简介&#xff1a;淘宝天猫详情接口API的功能及…

普通人搞副业,空闲时间做,月入5w+

我是电商珠珠 大家会发现&#xff0c;朱砂越来越火&#xff0c;不仅是因为它好看&#xff0c;而且商家对外扬言可以招财。现在的人对爱情不屑一顾&#xff0c;财神殿里可以长跪不起&#xff0c;人人都想求财&#xff0c;想要在空余时间搞副业赚大钱&#xff0c;但做什么还没有…

客服知识库到底好用在哪?企业真的需要吗?

在企业运营的众多环节中&#xff0c;客户服务无疑是至关重要的一环。然而&#xff0c;面对如洪水般涌入的客户问题和查询&#xff0c;你的客服团队是否能够做到快速应对&#xff0c;准确解答&#xff1f;这时&#xff0c;一个客服知识库就显得尤为重要。那么&#xff0c;客服知…

Java项目实战记录:雷达数据渲染

目录 Java项目实战记录&#xff1a;雷达数据渲染业务背景代码逻辑数据结构颜色渲染MapContent加载数据并输出截图 完整代码GenerateMapImage地图渲染工具测试代码 渲染效果 Java项目实战记录&#xff1a;雷达数据渲染 业务背景 我之前已经成功使用Java语言解析了C处理的雷达数…

Linux编程4.8 网络编程-建立连接

1、服务器端 #include <sys/types.h> #include <sys/socket.h>int listen(int sockfd, int backlog);返回&#xff1a;成功返回0&#xff0c;出错返回-1。参数&#xff1a;sockfd:套接字的文件描述符backlog:定义了sockfd的挂起连接队列可能增长的最大长度。…

鸿蒙4.0ArkUI快速入门(一)应用模型

ArkUI篇 应用模型Stage模型FA模型模型对比 应用模型 应用模型是HarmonyOS为开发者提供的应用程序所需能力的抽象提炼&#xff0c;它提供了应用程序必备的组件和运行机制。 HarmonyOS先后提供了两种应用模型&#xff1a; FA&#xff08;Feature Ability&#xff09;模型&…

Vue多文件学习项目综合案例——小兔鲜,黑马vue教程

文章目录 一、项目截图二、主要知识点三、Main.js四、App.vue五、componentsXtxBanner.vueXtxFooter.vueXtxHeaderNav.vueXtxHotBrand.vueXtxNewGoods.vueXtxShortCut.vueXtxTopic.vue 六、stylesbase.csscommon.css 一、项目截图 二、主要知识点 把静态页面拆分成一个个vue组…

Axure软件安装汉化教程

Axure软件安装汉化教程 一、准备教程 下载Axure的软件&#xff0c;并解压打开 二、安装过程 双击Axure软件的运行程序&#xff0c;修改安装程序的路径&#xff0c;默认下一步即可。 三、软件汉化 打开Axure的软件安装路径&#xff0c;将汉化包复制粘贴进入到Axure RP 9安装…

Web入门

一Spring简单介绍&#xff1a; Spring Boot 是基于Spring的但是&#xff0c;Spring更为简单高效。 1.2Spring Boot快速入门&#xff1a; 二HTTP协议&#xff1a; 2.1HTTP协议概述 2.2请求协议 <!DOCTYPE html> <html lang"en"> <head><meta ch…

Linux部署DockerUI结合内网穿透实现远程管理本地Docker容器

文章目录 前言1. 安装部署DockerUI2. 安装cpolar内网穿透3. 配置DockerUI公网访问地址4. 公网远程访问DockerUI5. 固定DockerUI公网地址 前言 DockerUI是一个docker容器镜像的可视化图形化管理工具。DockerUI可以用来轻松构建、管理和维护docker环境。它是完全开源且免费的。基…

文献速递:深度学习乳腺癌诊断---使用深度学习改善乳腺癌诊断的MRI技术

Title 题目 Improving breast cancer diagnostics with deep learning for MRI 使用深度学习改善乳腺癌诊断的MRI技术 01 文献速递介绍 乳腺磁共振成像&#xff08;MRI&#xff09;是一种高度敏感的检测乳腺癌的方式&#xff0c;报道的敏感性超过80%。传统上&#xff0c;其…

第六届国际大数据工程大会(BDE 2024)即将召开!

2024年第六届国际大数据工程大会(BDE 2024)将于2024年7月24-26日在中国西宁举行。本次会议由青海民族大学和中国矿业大学联合主办。BDE 2024旨在为大数据工程国际等领域的全球学术界、产业界和研究开发组织的研究人员提供一个交流平台&#xff0c;欢迎大数据领域的专家学者踊跃…