Chapter 4 Introduction (2) - preliminary algorithm
4.1 sorting
4.1.1 selection and sorting
This chapter is about simple selection sorting. It refers to enumerating elements A[1]~A[n] in sequence A from 1 to n for N times. Each time, select the smallest element from the part to be sorted [i,n] and exchange it with the first element A[i] of the part to be sorted. In this way, element A[i] will form A new ordered interval [1,i] with the current ordered interval [1,i-1]. So after n operations, all elements will be in order.
4.1.2 insert sort
Insertion sort is also the simplest sort method. This program mainly introduces the most intuitive insertion sort in insertion sort. Direct insertion sorting specifies that n elements A[1]~A[n] of sequence A are enumerated from 2 to N, and n-1 operations are performed. Suppose that the first I-1 elements A[1]~A[i-1] of A sequence have been ordered, but the range [i,n] has not been ordered. Then the trip looks for A certain position j from the range [1,i-1], so that after inserting A [i] into position J (at this time, A[j]~A[i-1] will move back to A[j+1]~A[i]), the sequence [1,i] is orderly.
Insertion sorting is the process of inserting the elements to be inserted into the initial ordered parts one by one, and the selection of insertion position follows the principle of maintaining order after insertion. The specific method is generally to enumerate the ordered parts from back to front to determine the insertion position.
4.1.3 application of sorting questions and sort function
Most of the sorting questions in the exam only need to get the final result of sorting. It is recommended to use the qsort function in c language or the sort function in c + + for efficient coding
1. Definition of related structures.
For sorting questions, many information of a question will be given in the title. These information will generally be used in the sorting process. Therefore, in order to facilitate coding, they are often stored in a structure, and then multiple individuals are represented by a structure array.
3. Implementation of ranking
Traverse the remaining individuals. If the score of the current individual is equal to the score of the previous individual, the ranking of the current individual is equal to the ranking of the previous individual; Otherwise, the ranking of the current individual is equal to the subscript of the array plus 1.
A1025
(1) Try it yourself
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 6 struct Student{ 7 char rn[15]; 8 int score; 9 int rank; 10 int ln; 11 int lr; 12 }stusTmp[310],stus[30010]; 13 14 bool cmp(Student a,Student b){ 15 if(a.score!=b.score) return a.score >b.score; 16 else return strcmp(a.rn,b.rn)<0; 17 } 18 19 int main(){ 20 int times; 21 scanf("%d",×); 22 int ln=0; 23 int totaln=0; 24 for(int i=0;i<times;i++){ 25 ln++; 26 int times2; 27 scanf("%d",×2); 28 for(int j=0;j<times2;j++){ 29 scanf("%s%d",stusTmp[j].rn,&stusTmp[j].score); 30 stusTmp[j].ln=ln; 31 } 32 sort(stusTmp,stusTmp+times2,cmp); 33 stusTmp[0].lr = 1; 34 for(int j=1;j<times2;j++){ 35 if(stusTmp[j].score ==stusTmp[j-1].score) stusTmp[j].lr =stusTmp[j-1].lr; 36 else stusTmp[j].lr= j+1; 37 } 38 for(int j=0;j<times2;j++){ 39 stus[j+totaln] =stusTmp[j]; 40 } 41 totaln+=times2; 42 } 43 sort(stus,stus+totaln,cmp); 44 stus[0].rank = 1; 45 printf("%d\n",totaln); 46 for(int j=1;j<totaln;j++){ 47 if(stus[j].score ==stus[j-1].score) stus[j].rank =stus[j-1].rank; 48 else stus[j].rank= j+1; 49 } 50 for(int j=0;j<totaln;j++){ 51 printf("%s %d %d %d\n",stus[j].rn,stus[j].rank,stus[j].ln,stus[j].lr); 52 } 53 }
In fact, it's not difficult after learning by yourself. The main mistake in the first attempt is to use the longlong type for the student number. There may be an admission card number starting with 0 in the test point, which can be changed to char.
To sum up some problems, we need to use sort function and strcmp function. We mainly clarify the idea of the problem and do it step by step.
B1015/A1062
(1) Try it yourself
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 6 struct Student{ 7 char id[15]; 8 int Dscore; 9 int Cscore; 10 int type; 11 }stus[100010],tmp; 12 13 bool cmp(Student a,Student b){ 14 if(a.type != b.type) return a.type<b.type; 15 else if(a.Dscore+a.Cscore != b.Cscore+b.Dscore) return a.Cscore+a.Dscore>b.Cscore+b.Dscore; 16 else if(a.Dscore!=b.Dscore) return a.Dscore>b.Dscore; 17 else return strcmp(a.id,b.id)<0; 18 19 } 20 21 int main(){ 22 int n,a1,a2; 23 scanf("%d%d%d",&n,&a1,&a2); 24 int okN=0; 25 for(int i=0;i<n;i++){ 26 scanf("%s%d%d",tmp.id,&tmp.Dscore,&tmp.Cscore); 27 if(tmp.Dscore>=a1 && tmp.Cscore>=a1){ 28 if(tmp.Dscore>=a2 && tmp.Cscore>=a2) tmp.type =1; 29 else if(tmp.Dscore>=a2) tmp.type =2; 30 else if(tmp.Dscore<a2 && tmp.Cscore<a2 && tmp.Dscore>=tmp.Cscore) tmp.type=3; 31 else tmp.type=4; 32 stus[okN] =tmp; 33 okN++; 34 } 35 } 36 sort(stus,stus+okN,cmp); 37 printf("%d\n",okN); 38 for(int i=0;i<okN;i++){ 39 printf("%s %d %d\n",stus[i].id,stus[i].Dscore,stus[i].Cscore); 40 } 41 }
At the beginning, the student array was small, and 10 ^ 5 was 100000. It's similar to the idea of the answer, that is, those who fail here are directly abandoned and passed.
A1012
(1) Reference answer
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <algorithm> 5 using namespace std; 6 7 struct Student{ 8 int id; 9 int grade[4]; 10 }stu[2010]; 11 12 char course[4] = {'A','C','M','E'}; 13 int Rank[10000000][4] = {0}; 14 int now; 15 16 bool cmp(Student a,Student b){ 17 return a.grade[now] > b.grade[now]; 18 } 19 20 int main(){ 21 int n,m; 22 scanf("%d%d",&n,&m); 23 for(int i=0;i<n;i++){ 24 scanf("%d%d%d%d",&stu[i].id,&stu[i].grade[1],&stu[i].grade[2],&stu[i].grade[3]); 25 stu[i].grade[0] = round((stu[i].grade[1]+stu[i].grade[2]+stu[i].grade[3] )/3); 26 } 27 for(now=0;now<4;now++){ 28 sort(stu,stu+n,cmp); 29 Rank[stu[0].id][now] = 1; //After sorting, set the highest score to rank1. 30 for(int i=1;i<n;i++){ 31 if(stu[i].grade[now]==stu[i-1].grade[now]){ 32 Rank[stu[i].id][now] = Rank[stu[i-1].id][now]; 33 } 34 else{ 35 Rank[stu[i].id][now]= i+1; 36 } 37 } 38 } 39 int query; //Query the candidate's child id 40 for(int i=0;i<m;i++){ 41 scanf("%d",&query); 42 if(Rank[query][0]==0){ 43 printf("N/A\n"); 44 }else{ 45 int k=0; 46 for(int j=0;j<4;j++){ 47 if(Rank[query][j]<Rank[query][k]){ 48 k=j; 49 } 50 } 51 printf("%d %c\n",Rank[query][k],course[k]); 52 } 53 } 54 }
This question depends directly on the answer. It's a question that tests the data structure. Copy the idea:
Idea:
Step 1: considering the priority A > C > M > e, you might as well assign the elements with sequence number 0 ~ 3 when setting the array, that is, 0 corresponds to A, 1 corresponds to C, 2 corresponds to M and 3 corresponds to E.
The 6-bit integer ID and 4 fractions are stored in the structure type Student (grade[0]~grade[3] represent a, C, m and e respectively).
Since the ID is a 6-bit integer, you may wish to set the Rank[1000000][4] array, where Rank[id][0]~Rank[id][3] represents the ranking of the four scores of the candidate with ID in all candidates. (the new array integrates all ranking data and ensures the order of candidate numbers, which has the advantage of random search. This can be achieved only when the candidate number is int).
Step 2: read in the candidate ID and 3 scores, and calculate the average score A at the same time.
Enumerate A, C, M and E in order, sort all candidates for each score, and record the ranking in the Rank array.
When querying, first check whether the read query ID exists (which can be determined by the initial value of Rank[i]). If it exists, select the one with the lowest number (i.e. the highest ranking) in Rank[id][0]~Rank[id][3].
The time complexity is O(nlogn).
This is a good answer to the database problem of the previous two days.
A1016
(1) Try it yourself
I got 15 points.. Look at the answer
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 6 struct Bill{ 7 char name[30]; 8 int MM; 9 int DD; 10 int HH; 11 int mm; 12 bool of; 13 bool skip=false; 14 }allBills[1010]; 15 16 bool cmp(Bill a,Bill b){ 17 if(strcmp(a.name,b.name)!=0) return strcmp(a.name,b.name)<0; 18 else if(a.MM!=b.MM) return a.MM<b.MM; 19 else if(a.DD!=b.DD) return a.DD<b.DD; 20 else if(a.HH!=b.HH) return a.HH<b.HH; 21 else return a.mm<b.mm; 22 } 23 24 //The filter function is not written first. 25 26 int count(int bg,Bill allBills[],int len){ 27 for(int i=bg;i<len-1;i++){ 28 if(strcmp(allBills[i].name,allBills[i+1].name)!=0) return i+1; 29 } 30 return -1; 31 } 32 33 34 void ignore(Bill allBills[],int n){ 35 if(allBills[0].of==false) allBills[0].skip=true; 36 for(int i=1;i<n;i++){ 37 if(i==n-1 && allBills[i].of==true) allBills[i].skip=true; 38 else if(allBills[i-1].of==allBills[i].of && allBills[i].of==false) allBills[i].skip=true; 39 else if(allBills[i-1].of==allBills[i].of && allBills[i].of==true) allBills[i-1].skip=true; 40 } 41 } 42 43 44 int main(){ 45 int charges[24]; 46 int canshu=0; 47 for(int i=0;i<24;i++){ 48 scanf("%d",&charges[i]); 49 canshu+=charges[i]; 50 } 51 int n; 52 scanf("%d",&n); 53 for(int i =0;i<n;i++){ 54 char tmpOf[30]; 55 scanf("%s %02d:%02d:%02d:%02d %s",allBills[i].name,&allBills[i].MM,&allBills[i].DD,&allBills[i].HH,&allBills[i].mm,tmpOf); 56 if(tmpOf[1]=='n') allBills[i].of = true; 57 else allBills[i].of =false; 58 } 59 sort(allBills,allBills+n,cmp); 60 int begin =0; 61 ignore(allBills,n); 62 int count1 = count(begin,allBills,n); 63 int sum=0; 64 printf("%s %02d\n",allBills[0].name,allBills[0].MM); 65 int jishu=0; 66 float total=0; 67 68 for(int i=0;i<n;i++){ 69 if(i==count1) 70 { 71 printf("%s %02d\n",allBills[i].name,allBills[i].MM); 72 begin =count1; 73 count1 = count(begin,allBills,n); 74 } 75 if(allBills[i].skip==true){ 76 if(i==count1-1 || i==n-1){ 77 printf("Total amount: $%.2f\n",total); 78 total=0; 79 } 80 continue; 81 } 82 jishu++; 83 if(jishu%2){ 84 int fenzhong=(allBills[i+1].DD-allBills[i].DD)*24*60; 85 int tmpSum=(allBills[i+1].DD-allBills[i].DD)*canshu*60; 86 for(int j=allBills[i].HH;j<=allBills[i+1].HH;j++){ 87 if(j==allBills[i].HH){ 88 tmpSum+=(60-allBills[i].mm)*charges[j]; 89 fenzhong+=60-allBills[i].mm; 90 } 91 else if(j==allBills[i+1].HH){ 92 tmpSum+=allBills[i+1].mm*charges[j]; 93 fenzhong+=allBills[i+1].mm; 94 } 95 else{ 96 tmpSum+=60*charges[j]; 97 fenzhong+=60; 98 } 99 } 100 printf("%02d:%02d:%02d %02d:%02d:%02d %d $%.2f\n",allBills[i].DD,allBills[i].HH,allBills[i].mm,allBills[i+1].DD,allBills[i+1].HH,allBills[i+1].mm,fenzhong,((float)tmpSum)/100); 101 total+=((float)tmpSum)/100; 102 } 103 if(i==count1-1 || i==n-1){ 104 printf("Total amount: $%.2f\n",total); 105 total=0; 106 } 107 } 108 }
(2) Reference answer
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn= 1010; 7 int toll[25]; 8 struct Record{ 9 char name[25]; 10 int month,dd,hh,mm; 11 bool status; 12 }rec[maxn],temp; 13 14 bool cmp(Record a,Record b){ 15 int s=strcmp(a.name,b.name); 16 if(s!=0) return s<0; 17 else if(a.month!=b.month) return a.month<b.month; 18 else if(a.dd!=b.dd) return a.dd<b.dd; 19 else if(a.hh!=b.hh) return a.hh<b.hh; 20 else return a.mm<b.mm; 21 } 22 23 void get_ans(int on,int off,int& time,int& money){ 24 temp= rec[on]; 25 while(temp.dd < rec[off].dd || temp.hh < rec[off].hh || temp.mm<rec[off].mm){ 26 time++; 27 money +=toll[temp.hh]; 28 temp.mm++; 29 if(temp.mm>=60){ 30 temp.mm=0; 31 temp.hh++; 32 } 33 if(temp.hh>=24){ 34 temp.hh=0; 35 temp.dd++; 36 } 37 } 38 } 39 int main(){ 40 for(int i=0;i<24;i++){ 41 scanf("%d",&toll[i]); 42 } 43 int n; 44 scanf("%d",&n); 45 char line[10]; 46 for(int i=0;i<n;i++){ 47 scanf("%s",rec[i].name); 48 scanf("%d:%d:%d:%d",&rec[i].month,&rec[i].dd,&rec[i].hh,&rec[i].mm); 49 scanf("%s",line); 50 if(strcmp(line,"on-line")==0){ 51 rec[i].status = true; 52 }else{ 53 rec[i].status =false; 54 } 55 } 56 //It's the same above 57 sort(rec,rec+n,cmp); 58 int on=0,off,next; //on and off For two paired records, next For the next user 59 while(on<n){ //Each cycle processes all records of a single user separately. 60 int needPrint =0; 61 next =on; 62 while(next<n && strcmp(rec[next].name,rec[on].name)==0){ 63 if(needPrint==0 && rec[next].status==true){ 64 needPrint =1; //find on，Set needPrint Is 1. 65 } 66 else if(needPrint==1 && rec[next].status==false){ 67 needPrint = 2; 68 } 69 next++; 70 } 71 if(needPrint <2){ //No matching found on-off 72 on = next; 73 continue; 74 } 75 int AllMoney =0; //The total cost. 76 printf("%s %02d\n",rec[on].name,rec[on].month); 77 while(on<next){ 78 while(on <next-1 79 && !(rec[on].status==true && rec[on+1].status==false)){ 80 on++; //Until you find a continuous on-line and off-line. 81 } 82 off = on +1; 83 if(off ==next){ //All paired have been output on-line and off-line 84 on=next; 85 break; 86 } 87 printf("%02d:%02d:%02d ",rec[on].dd,rec[on].hh,rec[on].mm); 88 printf("%02d:%02d:%02d ",rec[off].dd,rec[off].hh,rec[off].mm); 89 int time=0,money=0; 90 get_ans(on,off,time,money); 91 AllMoney += money; 92 printf("%d $%.2f\n",time,money/100.0); //Pay attention to the writing here. 93 on = off+1; 94 } 95 printf("Total amount: $%.2f\n",AllMoney/100.0); 96 } 97 return 0; 98 }
In fact, it is very similar to the writing method of sequence table. This question is essentially a sequence table.
Then the calculation method of time is also worth learning. It can be recited as a paradigm.
The condition for finding the two data to be printed is that the two data are continuous, and other situations can be ignored. There is also the problem of how to print money. It can be calculated per minute and then traversed. Let's put this question aside first. Look carefully when reviewing it. It's not so important and difficult.
A1028
(1) Try it yourself
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 6 struct Record{ 7 char ID[10]; 8 char name[10]; 9 int score; 10 }records[100010]; 11 12 bool cmp1(Record a,Record b){ 13 return strcmp(a.ID,b.ID)<0; 14 } 15 bool cmp2(Record a,Record b){ 16 if(strcmp(a.name,b.name)!=0) return strcmp(a.name,b.name)<0; 17 else return strcmp(a.ID,b.ID)<0; 18 } 19 bool cmp3(Record a,Record b){ 20 if(a.score!=b.score) return a.score<b.score; 21 else return strcmp(a.ID,b.ID)<0; 22 } 23 24 int main(){ 25 int n,c; 26 scanf("%d%d",&n,&c); 27 for(int i=0;i<n;i++){ 28 scanf("%s %s %d",records[i].ID,records[i].name,&records[i].score); 29 } 30 if(c==1) sort(records,records+n,cmp1); 31 else if(c==2) sort(records,records+n,cmp2); 32 else sort(records,records+n,cmp3); 33 for(int i=0;i<n;i++){ 34 printf("%s %s %d\n",records[i].ID,records[i].name,records[i].score); 35 } 36 }
There's nothing worth saying.
A1055
(1) Try it yourself
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 6 struct Record{ 7 char name[10]; 8 int age; 9 int worth; 10 }records[100010]; 11 12 bool cmp(Record a,Record b){ 13 if(a.worth != b.worth) return a.worth>b.worth; 14 else if(a.age!=b.age) return a.age<b.age; 15 else return strcmp(a.name,b.name)<0; 16 } 17 18 int main(){ 19 int n,k; 20 scanf("%d%d",&n,&k); 21 for(int i=0;i<n;i++){ 22 scanf("%s %d %d",records[i].name,&records[i].age,&records[i].worth); 23 } 24 sort(records,records+n,cmp); 25 for(int i=0;i<k;i++){ 26 printf("Case #%d:\n",i+1); 27 int nums,min,max; 28 scanf("%d%d%d",&nums,&min,&max); 29 int jishu=0; 30 for(int j=0;j<n;j++){ 31 if(jishu>=nums){ 32 break; 33 } 34 if(records[j].age>=min && records[j].age<=max){ 35 printf("%s %d %d\n",records[j].name,records[j].age,records[j].worth); 36 jishu++; 37 } 38 if(j==n-1 && jishu==0){ 39 printf("None\n"); 40 } 41 } 42 } 43 }
There is a preprocessing method in the answer. If the number of people of a certain age is less than 100, it will be stored in the new array. If more than 100 is deleted directly, it can save the time consumed by query, and it is also a good processing method in database writing.
A1075
(1) Try it yourself
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 6 struct Record{ 7 int rank; 8 int ID; 9 int probs[7]={-2,-2,-2,-2,-2,-2,-2}; 10 int score; 11 int score2; 12 int pvs; 13 }records[10010]; 14 15 bool cmp(Record a,Record b){ 16 if(a.score!=b.score) return a.score>b.score; 17 else if(a.pvs!=b.pvs) return a.pvs>b.pvs; 18 else return a.ID<b.ID; 19 } 20 21 int main(){ 22 int n,k,m; 23 scanf("%d%d%d",&n,&k,&m); 24 int scores[k]; 25 for(int i=0;i<k;i++){ 26 scanf("%d",&scores[i]); 27 } 28 for(int i=0;i<m;i++){ 29 int tmpID,tmpProb,tmpScore; 30 scanf("%d%d%d",&tmpID,&tmpProb,&tmpScore); 31 records[tmpID-1].ID =tmpID; 32 if(tmpScore==scores[tmpProb-1] && records[tmpID-1].probs[tmpProb-1]!=scores[tmpProb-1]) records[tmpID-1].pvs++; 33 if(tmpScore>records[tmpID-1].probs[tmpProb-1]) records[tmpID-1].probs[tmpProb-1]=tmpScore; 34 } 35 for(int i=0;i<n;i++){ 36 for(int j=0;j<k;j++){ 37 if(records[i].probs[j]!=-1 && records[i].probs[j]!=-2) records[i].score+=records[i].probs[j]; 38 if(records[i].probs[j]==-1 || records[i].probs[j]==-2) records[i].score2+=1; 39 } 40 } 41 sort(records,records+n,cmp); 42 records[0].rank =1; 43 for(int i=0;i<n-1;i++){ 44 if(records[i].score>records[i+1].score) records[i+1].rank =i+2; 45 else records[i+1].rank = records[i].rank; 46 } 47 for(int i=0;i<n;i++){ 48 if(records[i].score2!=k){ 49 printf("%d %05d %d",records[i].rank,records[i].ID,records[i].score); 50 for(int j=0;j<k;j++){ 51 if(records[i].probs[j]==-2) printf(" -"); 52 else if(records[i].probs[j]==-1) printf(" 0"); 53 else printf(" %d",records[i].probs[j]); 54 } 55 printf("\n"); 56 } 57 } 58 }
The last test point requires multiple full scores of single questions, and the full scores are not recorded repeatedly.