I have encountered a problem today. The topic is as follows:
Sum
Time Limit: 30 SecondsMemory Limit: 32768k bytesubmitted: 375accepted: 44
Summr. Jojer is Given N Numbers and an extra integer x, He Wants to know WHETER THERE ARE TWO NUMBERS whose Sum is x.
InputThe Input File Contains Several Test Cases. The First Cases. The First Line of Each Test Case Contains Two Integers, N (<= 1000001) and x. From the next line of each test case, There is n number.
Outputach Test Case Corresponds to a line in The Output, Which IS Either "YES" if the exists an aff.0. "No" if not.
Sample Input
3 3
1 2 3
twenty three
1 3
Sample Output Yesno
Submit Your Solution
As can be seen from topic, it is desirable that the number of integers to X is required in more than 100,000 integers, and its calculation amount is very huge. The topic requires that a number of items completed in 30 seconds ( Several groups). If a general cycle is 2-order, it is not yet. I have two sets of solutions.
1. In order to replace the speed. In order to improve the speed of operation, first, it should be thought of in exchange for time at the time of the time. The most embodied is the Hash table that is learning in our data structure .hash table. Finding speed is very fast, maybe we use how to apply the Hash table here? I use a relatively stupid method. Cyclicity Each element in each group, first check if its value exists in a Hash table, if present, description "YES ". Otherwise insert the value of the X-element into a Hash table. So, I only need a 1-order algorithm to complete. However, this hash table is very huge. However, we only need to put an integer within a general range into the Hash table, and if the range of values exceeds the range of HASH, it is individually stored in a linear table. Below is the source program I have already debugged, and accpeted on the ACM Online Judge. #include
#define max_n 3000002long integers [MAX_N];
Char regularTab [MAX_N]; Long ExtendTab [MAX_N]; Long Numext;
Long n; long x;
Void INSERTTAB (INT A); int Lookup (INT A);
INT main () {long i, j; long m; int yes; while (scanf ("% ld% ld", & n, & x) == 2) {MEMSET (RegularTab, 0, max_n); MEMSET (ExtendTab, 0 , MAX_N * SIZEOF (long); Numext = 0; yes = 0;
For (i = 0; i For (i = 0; i Void InsertTab (INT A) {IF (A> -max_n / 2 && a INT LOOKUP (INT A) {IF (A> -max_n / 2 && a 2. The algorithm that uses the Quicksort and QSort function quickly sorted more. A compilation level QSort function has been provided in the C language stdlib.h. This problem uses rapid sorting method is to let all the numbers first sorted first, then look for. Although sorting is also a second order algorithm, due to the specialty of Quicksort, the process of sorting is still relatively fast. Once the sort is complete, it can be done according to X, and it can be completed. I don't have any of the specific implementation. However, I think the use of QSort is very important, so I plagonize the sample code of the QSORT function from MSDN. Void Qsort Void * base, Size_t Num, SIZE_T WIDTH, INT (__cdecl * compare) (const void *, const void *) ); EXAMPLE // CRT_QSORT.C // arguments: Every Good Boy Deserves Favor / * This Program Reads the command-line * Parameters and uses qsort to sort theme. IT * The Displays the sorted arguments. * / #include #include #include INT COMPARE (const void * arg2); INT main (int Argc, char ** argv) { INT I; / * ELIMINATE ARGV [0] from sort: * / Argv ; Argc-- / * Sort remaining args using quicksort algorithm: * / Qsort ((void *) argv, (size_t) argc, sizeof (char *), compare; / * OUTPUT SORTED LIST: * / For (i = 0; i Printf ("% s", argv [i]); Printf ("/ n"); } INT COMPARE (const void * arg1, const void * arg2) { / * Compare All of Both strings: * / Return_Stricmp (* (char **) arg1, * (char **) arg2); } OUTPUT Boy Deserves Every Favor Good
