who didn't finish the experiment?
A semester is over, the teacher want to know whether some of my classmates is a computer experimental all didn't, which is never submitted an application, now the teacher submit records of all the classmates were derived from the platform, and have already according to the serial number of students from small to large, sorted by now give you the serial number of some of my classmates, help the teacher to see if the students have to submit records,
input format:
The first line of an integer N, said the number of all submissions (0 & lt; N<=2000000),
The following N lines, said every time to submit the corresponding number A student? i?? , (0 & lt; A? i?? <=1000000),
The next line, an integer M, said to query the number of students M (0 & lt; M<=10000),
The next M lines, each line a student number (the number in the range of int),
The output format:
Output "Yes" or "No", said the number of the students ever submit records, output (not including the quotes)
My code:

 # include 
Int main () {
int n;//the first line of input digital, said all submissions number 
The scanf (" % d ", & amp; N); 
Int a [n]. 
int i; 
for(i=0; i The scanf (" % d ", & amp; A [I]);//input presented corresponding student no. 
} 
int m; 
The scanf (" % d ", & amp; M);//said to query the number of students 
Int b [m]; 
Int flag=0; 
int j; 
for(j=0; J & lt; m; J++) {
The scanf (" % d ", & amp; B [j]); 
} 
for(j=0; J & lt; m; J++) {
for(i=0; i If (a [I]==b [j]) {
Flag=1; 
} 
} 
If (flag==1) {
Printf (" Yes \ n "); 
} else {
Printf (" \ n "); 
} 
} 
return 0; 
} 

Prompted to run the timeout, how should I do?

CodePudding user response:

N=2000000 m=10000
The two layers of cycle you is the n * m=20000000000
It is certainly a timeout!
A? i?? <=1000000, you use an array of tag students ever submit, should be ok

CodePudding user response:

It is sorted, so you can use binary search, an id up to dozens of times over

CodePudding user response:

If memory is enough, can also be bitmap

CodePudding user response:

According to the analysis, in one million the size of the byte array to represent all the students submit a record, it will take about 1 MB memory, query time complexity is O (1),