誰沒有完成實驗？
一個學期結束了，老師想知道一些同學是否一次上機實驗都沒進行，也就是沒提交過一次程式。現在老師從平臺匯出了所有同學的提交記錄，并已經按照學生的編號從小到大排好序了，現在給你一些同學的編號，幫老師看看這些同學是否有提交記錄。
輸入格式:
第一行一個整數N，表示所有提交的次數(0<N<=2000000)。
以下N行，表示每次提交對應的學生編號A?i?? ,(0<A?i?? <=1000000)。
接下來一行，一個整數M，表示要查詢學生的數量M(0<M<=10000)。
接下來M行，每行一個學生編號（編號在int范圍內）。
輸出格式:
輸出“Yes”或者“No”表示該編號學生是否有過提交記錄。（輸出不包括引號）
我的代碼：
#include<stdio.h>
int main(){
int n;//第一行輸入的數字，表示所有提交次數
scanf("%d",&n);
int a[n];
int i;
for(i = 0; i < n;i++){
scanf("%d",&a[i]);//輸入每次提交對應的學生編號
}
int m;
scanf("%d",&m);//表示要查詢學生的數量
int b[m];
int flag = 0;
int j;
for(j = 0; j < m; j++){
scanf("%d",&b[j]);
}
for(j = 0; j < m; j++){
for(i = 0; i < n; i++){
if(a[i]==b[j]){
flag = 1;
}
}
if(flag == 1){
printf("Yes\n");
}else{
printf("No\n");
}
}
return 0;
}
系統提示運行超時，我該怎么辦呢？
uj5u.com熱心網友回復：
n=2000000 m=10000那你兩層回圈就是n*m=20000000000次
這肯定超時啊
A?i?? <=1000000，你用陣列標記學生是否提交過，應該就可以
uj5u.com熱心網友回復：
因為是排好序的，所以可以用二分查找，一個id最多幾十次就結束了uj5u.com熱心網友回復：
要是記憶體足夠，也可以bitmap的方式uj5u.com熱心網友回復：
根據題目分析，用一百萬大小的byte陣串列示所有的學生提交記錄即可，大約需要記憶體1MB，查詢時間復雜度為O（1）。轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/55047.html
標籤：C語言
上一篇：反射之類加載器（1）