心得

遇到運行時間超時，首先要判斷是真的超時（數據量大，算法時間復雜度高），還是因為程序本身的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;//temppstu 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;//depcur1->de = pcur2->de;pcur2->de = de_temp;cai_temp = pcur1->cai;//caipcur1->cai = pcur2->cai;pcur2->cai = cai_temp;total_score_temp = pcur1->total_score;//total_scorepcur1->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;//numpbefore->num = pcur->num;pcur->num = temp.num;temp.de = pbefore->de;//depbefore->de = pcur->de;pcur->de = temp.de;temp.cai = pbefore->cai;//caipbefore->cai = pcur->cai;pcur->cai = temp.cai;temp.total_score = pbefore->total_score;//total_scorepbefore->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;//numpbefore->num = pcur->num;pcur->num = temp.num;temp.de = pbefore->de;//depbefore->de = pcur->de;pcur->de = temp.de;temp.cai = pbefore->cai;//caipbefore->cai = pcur->cai;pcur->cai = temp.cai;temp.total_score = pbefore->total_score;//total_scorepbefore->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;//numpbefore->num = pcur->num;pcur->num = temp.num;temp.de = pbefore->de;//depbefore->de = pcur->de;pcur->de = temp.de;temp.cai = pbefore->cai;//caipbefore->cai = pcur->cai;pcur->cai = temp.cai;temp.total_score = pbefore->total_score;//total_scorepbefore->total_score = pcur->total_score;pcur->total_score = temp.total_score;}pbefore = pcur;//小弟記錄大哥的腳印pcur = pcur->pnext;//大哥先走一步}}//總分排序后打印list_print(phead, ptail);//遍歷鏈表手動打印(嚴格限制條件，避免重復打印，注意邊界等號)//第一遍打印：cai>H && de>Hprintf("第一遍打印\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>=Hprintf("第二遍打印\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>caiprintf("第三遍打印\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<=caiprintf("第四遍打印\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"); } 超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的关于牛客网运行超时的原因分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。