关于牛客网运行超时的原因分析_寒泉Hq的博客-程序员宅基地_牛客网运行超时

技术标签: 超时  牛客网  C语言  

心得

遇到运行时间超时,首先要判断是真的超时(数据量大,算法时间复杂度高),还是因为程序本身的bug(在特定的测试用例中出现了死循环、使用了system("pause"))而出现的问题。

如何找到超时的原因?

在不影响整体运行的情况下,可以尝试在OJ上一点一点删除代码段,直至出现运行结果错误,而非超出时间限制。同时注意查看当前运行结果的运行时间。这样通过排除法,就能找出是哪一部分代码导致了超时。

问题(未解决)

提交了一段代码,如下(仅做测试,运行结果无意义):
从后往前看,最后一个for循环,i的范围是0~1700时,就已经出现了超出时间限制1000ms的情况(如下图)。
从图中看到,仅1700次循环就花了900ms
而真正的测试用例有100000个数,肯定超时了
分析原因可能是calloc耗费时间过长。有人说一次calloc耗时大约相当于1000次for循环。每一个新的结构体都重新申请内存,太浪费时间了?
解决思路
定义结构体数组,而不是每一次都calloc

#include<stdio.h>
#include<stdlib.h>
typedef struct student
{
    
	long int num;
	int de;
	int cai;
	int total_score;
	struct student *pnext;
}stu, *pstu;
//增加
void list_insert_tail(pstu *pphead, pstu *pptail, long int num, int de, int cai)
{
    
	pstu pnew;
	pnew = (pstu)calloc(1, sizeof(stu));
	pnew->num = num;
	pnew->de = de;
	pnew->cai = cai;
	pnew->total_score = de + cai;
	if (NULL == *pptail)//如果链表为空
	{
    
		*pphead = pnew;
		*pptail = pnew;//不用担心尾节点不是NULL,因为calloc的pnew中的pnext成员本身就是null
	}
	else
	{
    
		(*pptail)->pnext = pnew;//原有链表尾的pnext成员指向新节点
		*pptail = pnew;//新节点成为新的链表尾
	}
}

int main()
{
    
	int total;
	int L;//最低录取线
	int H;//优先录取线
	int i = 0;
	stu student;
	pstu phead = NULL;
	pstu ptail = NULL;
	scanf("%d %d %d", &total, &L, &H);
	//输入
	while (i != total)
	{
    
		scanf("%ld %d %d", &student.num, &student.de, &student.cai);
		list_insert_tail(&phead, &ptail, student.num, student.de, student.cai);//尾插法
		i++;
	}
	//对总分排序:冒泡------------------------------------(这一段在牛客网上不能运行)
	pstu pcur = phead;
	pstu pbefore;
	stu temp;
    //按学号排序
	for (i = 0; i < 1700; i++)
	{
    
		pcur = phead;
		pbefore = pcur;
		while (pcur != NULL)
		{
    
			pbefore = pcur;//小弟记录大哥的脚印
			pcur = pcur->pnext;//大哥先走一步
		}
    }
}

在这里插入图片描述
附上本地可以运行的代码,以及做题笔记

笔记

输入第1行给出3个正整数,分别为:
N(<=105),即考生总数;
L(>=60),为录取最低分数线,即德分和才分均不低于L的考生才有资格被考虑录取;
H(<100),为优先录取
德分和才分均不低于此线的被定义为“才德全尽”,此类考生按德才总分从高到低排序;
才分不到但德分到线的一类考生属于“德胜才”,也按总分排序,但排在第一类考生之后;
德才分均低于H,但是德分不低于才分的考生属于“才德兼亡”但尚有“德胜才”者,按总分排序,但排在第二类考生之后;
其他达到最低线L的考生也按总分排序,但排在第三类考生之后。
随后N行,每行给出一位考生的信息,包括:准考证号、德分、才分,其中准考证号为8位整数,德才分为区间[0, 100]内的整数。数字间以空格分隔。
才德全尽: 才>80,德>80 总分从高到低排序
德胜才: 才<80,德>80 总分从高到低排序
才德兼亡,德胜才 才<80,德<80 总分从高到低排序
德>才
才德兼亡,德不胜才 才<80,德<80 总分从高到低排序
德<才
证号、德分、才分
输入
14 60 80
10000001 64 90
10000002 90 60
10000011 85 80
10000003 85 80
10000004 80 85
10000005 82 77
10000006 83 76
10000007 90 78
10000008 75 79
10000009 59 90
10000010 88 45
10000012 80 100
10000013 90 99
10000014 66 60
输出(总分相同时,德高排前面)
证号、德分、才分
才>80,德>80
10000013 90 99 189
10000012 80 100 180
10000003 85 80 165
10000011 85 80 165
10000004 80 85 165
才<80,德>80
10000007 90 78 168
10000006 83 76 159
10000005 82 77 159
10000002 90 60 150
才<80,德<80,德>才
10000014 66 60 126
才<80,德<80,德<才
10000008 75 79 154
10000001 64 90 154

代码

//本地测试可以运行,牛客网上测试用例数据量大,超出时间限制
//函数"交换两个节点的值"没用,仅留其思想,运行时可以删除
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
typedef struct student
{
    
	long int num;
	int de;
	int cai;
	int total_score;
	struct student *pnext;
}stu, *pstu;

//打印
void list_print(pstu phead, pstu ptail)
{
    
	printf("打印:\n");
	pstu pcur = phead;
	while (pcur != NULL)
	{
    
		printf("%ld %d %d %d\n", pcur->num, pcur->de, pcur->cai, pcur->total_score);
		pcur = pcur->pnext;
	}
	printf("\n");
}

//增加
void list_insert_tail(pstu *pphead, pstu *pptail, long int num, int de, int cai)
{
    
	pstu pnew;
	pnew = (pstu)calloc(1, sizeof(stu));
	pnew->num = num;
	pnew->de = de;
	pnew->cai = cai;
	pnew->total_score = de + cai;
	if (NULL == *pptail)//如果链表为空
	{
    
		*pphead = pnew;
		*pptail = pnew;//不用担心尾节点不是NULL,因为calloc的pnew中的pnext成员本身就是null
	}
	else
	{
    
		(*pptail)->pnext = pnew;//原有链表尾的pnext成员指向新节点
		*pptail = pnew;//新节点成为新的链表尾
	}
}

//删除i
void list_delete(pstu *pphead, pstu *pptail, int i,int *total)
{
    
	pstu pcur = *pphead;
	pstu pbefore = *pphead;
	if (NULL == *pptail)//如果链表为空
	{
    
		printf("链表为空\n");
	}
	else if (i == (*pphead)->de || i == (*pphead)->cai)//如果等于第一个节点(此时可能仅剩一个节点)
	{
    
		*pphead = (*pphead)->pnext;//头指针指向下一个节点
		*total = *total - 1;
		if (NULL == *pphead)
		{
    
			*pptail = NULL;
			free(pcur);
		}
	}
	else//如果不等于第一个节点
	{
    
		while (NULL != pcur)//只要不是最后
		{
    
			if (i == pcur->de || i == pcur->cai)//如果等于当前节点
			{
    
				pcur = pcur->pnext;//大哥前进一步
				pbefore->pnext = pcur;//小弟的pnext成员指向大哥
				return;
			}
			else
			{
    
				pbefore = pcur;//小弟记住大哥的脚印
				pcur = pcur->pnext;//大哥先走一步		
			}
		}
		if (NULL == pcur)//如果到最后
		{
    
			//			printf("不存在此数字\n");
		}
	}
}
//交换两个节点的值:num_before,num_after分别是要交换的两个学号
void list_switch(pstu *pphead, pstu *pptail, long int num_before, long int num_after)
{
    

	int de_temp, cai_temp, total_score_temp;//temp
	pstu pcur1 = *pphead;
	pstu pcur2 = *pphead;
	pstu pbefore1 = *pphead;
	pstu pbefore2 = *pphead;
	if (NULL == *pptail)//如果链表为空
	{
    
		printf("链表为空\n");
	}
	else
	{
    
		while (NULL != pcur1)//只要不是最后
		{
    
			if (num_before == pcur1->num)//如果num_before等于1当前节点的num成员
			{
    
				while (NULL != pcur2)//找交换目标节点
				{
    
					if (num_after == pcur2->num)//如果num_after等于2当前节点的num成员,交换
					{
    
						de_temp = pcur1->de;//de
						pcur1->de = pcur2->de;
						pcur2->de = de_temp;
						cai_temp = pcur1->cai;//cai
						pcur1->cai = pcur2->cai;
						pcur2->cai = cai_temp;
						total_score_temp = pcur1->total_score;//total_score
						pcur1->total_score = pcur2->total_score;
						pcur2->total_score = total_score_temp;
					}
					else//如果2当前节点不是要找的节点,向后走一步
					{
    
						pbefore2 = pcur2;//小弟记住大哥的脚印
						pcur2 = pcur2->pnext;//大哥先走一步		
					}
					if (NULL == pcur2)//如果2当前节点到最后
					{
    
						printf("不存在此数字\n");
					}
				}
				return;
			}
			else//如果2当前节点不是要找的节点,向后走一步
			{
    
				pbefore1 = pcur1;//小弟记住大哥的脚印
				pcur1 = pcur1->pnext;//大哥先走一步		
			}
		}
		if (NULL == pcur1)//如果1当前节点到最后
		{
    
			printf("不存在此数字\n");
		}
	}
}

int main()
{
    
	int total;
	int L;//最低录取线
	int H;//优先录取线
	int i = 0;
	stu student;
	pstu phead = NULL;
	pstu ptail = NULL;
	scanf("%d %d %d", &total, &L, &H);
	//输入
	while (i != total)
	{
    
		scanf("%ld %d %d", &student.num, &student.de, &student.cai);
		list_insert_tail(&phead, &ptail, student.num, student.de, student.cai);//尾插法
		i++;
	}
	//删除不合格节点
	for (i = 1; i < L; i++)
	{
    
		list_delete(&phead, &ptail, i,&total);
	}
	list_print(phead, ptail);
	//对总分排序:冒泡------------------------------------(这一段在牛客网上不能运行)
	pstu pcur = phead;
	pstu pbefore;
	stu temp;
	int j;
	//按学号排序
	for (i = 0; i < total; i++)
	{
    
		pcur = phead;
		pbefore = pcur;
		pcur = pcur->pnext;
		for (j = 0; j < total&& pcur != NULL; j++)
		{
    
			if (pbefore->num > pcur->num)//交换两个结构体的值(改变了链表的顺序)
			{
    
				temp.num = pbefore->num;//num
				pbefore->num = pcur->num;
				pcur->num = temp.num;
				temp.de = pbefore->de;//de
				pbefore->de = pcur->de;
				pcur->de = temp.de;
				temp.cai = pbefore->cai;//cai
				pbefore->cai = pcur->cai;
				pcur->cai = temp.cai;
				temp.total_score = pbefore->total_score;//total_score
				pbefore->total_score = pcur->total_score;
				pcur->total_score = temp.total_score;
			}
			pbefore = pcur;//小弟记录大哥的脚印
			pcur = pcur->pnext;//大哥先走一步
		}
	}
	//按总分排序
	for (i = 0; i < total; i++)
	{
    
		pcur = phead;
		pbefore = pcur;
		pcur = pcur->pnext;
		for (j = 0; j < total&& pcur != NULL; j++)
		{
    
			if (pbefore->total_score < pcur->total_score)//交换两个结构体的值(改变了链表的顺序)
			{
    
				temp.num = pbefore->num;//num
				pbefore->num = pcur->num;
				pcur->num = temp.num;
				temp.de = pbefore->de;//de
				pbefore->de = pcur->de;
				pcur->de = temp.de;
				temp.cai = pbefore->cai;//cai
				pbefore->cai = pcur->cai;
				pcur->cai = temp.cai;
				temp.total_score = pbefore->total_score;//total_score
				pbefore->total_score = pcur->total_score;
				pcur->total_score = temp.total_score;
			}
			pbefore = pcur;//小弟记录大哥的脚印
			pcur = pcur->pnext;//大哥先走一步
		}
	}
	//若总分相同,按de排序
	for (i = 0; i < total; i++)
	{
    
		pcur = phead;
		pbefore = pcur;
		pcur = pcur->pnext;
		for (j = 0; j < total && pcur != NULL; j++)
		{
    
			if (pbefore->total_score == pcur->total_score && pbefore->de < pcur->de)//如果相邻两个节点总分相同,前者de小于后者,则交换两个节点
			{
    
				temp.num = pbefore->num;//num
				pbefore->num = pcur->num;
				pcur->num = temp.num;
				temp.de = pbefore->de;//de
				pbefore->de = pcur->de;
				pcur->de = temp.de;
				temp.cai = pbefore->cai;//cai
				pbefore->cai = pcur->cai;
				pcur->cai = temp.cai;
				temp.total_score = pbefore->total_score;//total_score
				pbefore->total_score = pcur->total_score;
				pcur->total_score = temp.total_score;
			}
			pbefore = pcur;//小弟记录大哥的脚印
			pcur = pcur->pnext;//大哥先走一步
		}
	}
	//总分排序后打印
	list_print(phead, ptail);
	//遍历链表手动打印(严格限制条件,避免重复打印,注意边界等号)
	//第一遍打印:cai>H && de>H
	printf("第一遍打印\n");
	pcur = phead;
	while (pcur != NULL)
	{
    
		if (pcur->cai >= H && pcur->de >= H)printf("%ld %d %d %d\n", pcur->num, pcur->de, pcur->cai, pcur->total_score);
		pcur = pcur->pnext;
	}
	//第二遍打印: cai<H && de>=H
	printf("第二遍打印\n");
	pcur = phead;
	while (pcur != NULL)
	{
    
		if (pcur->cai < H && pcur->de >= H)printf("%ld %d %d %d\n", pcur->num, pcur->de, pcur->cai, pcur->total_score);
		pcur = pcur->pnext;
	}
	//第三遍打印: cai<=H && de<=H && de>cai
	printf("第三遍打印\n");
	pcur = phead;
	while (pcur != NULL)
	{
    
		if (pcur->cai <= H && pcur->de <= H && pcur->de >= pcur->cai)printf("%ld %d %d %d\n", pcur->num, pcur->de, pcur->cai, pcur->total_score);
		pcur = pcur->pnext;
	}
	//第四遍打印: cai<=H && de<=H && de<=cai
	printf("第四遍打印\n");
	pcur = phead;
	while (pcur != NULL)
	{
    
		//if(pcur->cai <= H && pcur->de <= H && pcur->de < pcur->cai)printf("%ld %d %d %d\n", pcur->num, pcur->de, pcur->cai, pcur->total_score);
		if (pcur->de < H && pcur->de < pcur->cai)printf("%ld %d %d %d\n", pcur->num, pcur->de, pcur->cai, pcur->total_score);
		pcur = pcur->pnext;
	}
	system("pause");
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/sinat_42483341/article/details/86709328

智能推荐

2013年工作中遇到的20个问题:1-20_weixin_34315485的博客-程序员宅基地

2019独角兽企业重金招聘Python工程师标准&gt;&gt;&gt; ...

Mac 终端命令行启动自带的python和自带的idle_huxinguang002的博客-程序员宅基地_mac python启动命令

1、启动python查看Mac自带python的路径:终端输入$ which python打开路径在Finder中进入路径 /usr/bin/python双击这个exec可执行文件就可以打开python了(也可以直接在终端输入 $ open /usr/bin/python),终端会弹出Python的窗口 2、启动idleMac自带的idle的路径跟其自带的python处于同级目录,即 /usr/

C语言 函数不定长参数 - C语言零基础入门教程_猿说编程的博客-程序员宅基地

目录一.前言二.函数不定长参数简介1.va_start2.va_arg3.va_end三.自定义不定长参数的函数1.va_start/va_arg/va_end 案例一2.va_start/va_arg/va_end 案例二四.猜你喜欢零基础 Python 学习路线推荐 : C/C++ 学习目录 &gt;&gt; C 语言基础入门一.前言对 printf 函数的使用,我们并不陌生,首先我们来看看下面关于 printf 函数的几种调用方式:printf("hell

寻找迷宫出口<一>_John__xs的博客-程序员宅基地

寻找迷宫出口小程序目的: 判断在一个10*10的矩阵中是否可以找到迷宫的出口;PS:程序功能比较单一,还有许多可以改进的地方,比如,可以寻找出口的最优路径,可是我现在没有想出来,所以,在 寻找迷宫出口 我会对迷宫问题做出进一步的完善!---------------------------------------------------------

Silverlight 数据绑定(Binding) _ZetaChow晓代码的博客-程序员宅基地

    在使用Silverlight进行开发的时候,会觉得数据的操作是在是非常简单,不管是用WCF还是Webclient在于服务器通信后,Silverlight处理并显示数据都非常的方便,TextBlock TextBox等控件的使用方法也很容易掌握,但是,Silverlight依旧按照.net的传统提供了数据绑定的功能,使用数据绑定可以让Silverlight的数据操作更加灵活,有序。 

剑指Offer(Java实现):数组中重复的数字_JohnnyDeng94的博客-程序员宅基地

最近刚刚结束面试,来到了北京,很开心~准备面试的过程中看了剑指Offer这本书,想尽可能的整理一些代码的Java实现。在自己看书之前,也看到过很多大牛对剑指Offer这本书的代码使用Java重新实现了。这里只是我个人对题目的理解和实现,而且实现出的代码我也会尽可能的跑出各种用例来保证准确度。如有错误,劳烦各位大佬指出~如果觉得我的代码写的不是很好,请推荐给我大佬写过的来学习一波~packag...

随便推点

Java-springboot生鲜电商项目(三)商品分类模块_bingbing0607的博客-程序员宅基地

Java-springboot生鲜电商项目(二)商品分类模块主要功能主要会使用的新技术有:(一)开发添加商品分类目录的接口1.在MallExceptionEnum加入处理异常的相关代码2.在dao层CategoryMapper中添加通过商品类目名查询的接口3.在categoryMapper.xml中添加SQL语句4.另外添加目录请求类,不用pojo中Category,是因为保持每个类都有自己的职责,也是保证程序的安全性5.在Service下创建目录分类的Service接口,并创建CategoryImpl实现

LINUX 下tcp 和 udp 套接字收发缓冲区的大小决定规则_qiaoliang328的博客-程序员宅基地_如何确定 udp 套接字发送和接收报文时,所允许的最小和最大缓冲区 的大小

1. tcp 收发缓冲区默认值 [[email protected] core]# cat /proc/sys/net/ipv4/tcp_rmem  4096    87380   416153687380  :tcp接收缓冲区的默认值 [[email protected] core]# cat /proc/sys/net/ipv4/tcp_wmem 4096    16384   416153616

六十四卦_baijiong4223的博客-程序员宅基地

易经六十四卦,是西伯侯姬昌(周文王)被纣王囚禁关押的七年间,在狱中潜心研究伏羲八卦,在八卦的基础上推演所创的。所以又称为周易六十四卦。中文名六十四卦类别风水出处《周易》组成由两个八卦上下组合而成发明人周文王六十四卦词义辨析编辑六十四卦 方图六十四卦:周易里的六十四卦...

CMMI学习笔记_ForestWorld的博客-程序员宅基地

CMMI: 全称是Capability Maturity Model Integration,即能力成熟度模型集成(也有称为:软件能力成熟度集成模型)是美国卡内基梅隆大学软件工程研究所(SEI)应美国联邦政府的要求,于1991年开发出来的一种用于评价软件承包商能力并帮助其改善质量的方法【4】本质是软件管理工程的一个部分,其目的是帮助企业对软件工程过程进行管理和改进,增强开发与改进能力,从而能按...

密码加盐_匠子的博客-程序员宅基地

今天看到一个新鲜词:Salting password,加盐的密码。感觉很是纳闷,这是什么意思呢?上网查了下原来是对密码进行一些混淆增加破解的难度。        一般对密码都不会是明文存储,而是对密码进行MD5处理,增强反向解密难度。但这样还是能可以找出破绽。如果用户可以查看数据库,那么他可以观察到自己的密码和别人的密码加密后的结果都是一样,那么,就会知道别人用的和自己就是同一个密码。

职工管理系统_ailemao4747的博客-程序员宅基地

一丶利用以前学习的函数编辑这个系统。二、功能结构职工信息管理系统开始 1按职工号查询 2按学历查询 3按号码查询 2按职工姓名删除 1按职工号删除 2按职工姓名修改 1按职工号修改 菜单 根据菜单输入的值选择程序 1 录入职工信息 2 浏览职工信息 3 查询职工信息 5 添加职工信息 4 删除职工信息 6 修改职工信息 7 退出三丶目的:要求熟练掌握C语言的基本知识和编辑技能。基本掌握结...

推荐文章

热门文章

相关标签