@[TOC]
Contest100000581 - 《算法筆記》4.1小節(jié)——算法初步->排序
1、講解
4.1 .1 選擇排序
選擇排序
4.1.2 插入排序
插入排序
4.1.3 排序題與sort()函數(shù)的應(yīng)用
1.相關(guān)結(jié)構(gòu)體的定義
相關(guān)結(jié)構(gòu)體的應(yīng)用
2.cmp函數(shù)的編寫
cmp函數(shù)
3.排名的實(shí)現(xiàn)
排名實(shí)現(xiàn)
2、例題
PATA 1025:
https://pintia.cn/problem-sets/994805342720868352/problems/994805474338127872
題析：很經(jīng)典的題目，值得反復(fù)咀嚼
//1025PAT Ranking
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct student//學(xué)生結(jié)構(gòu)體
{
char id[15];//準(zhǔn)考證號(hào)
int score;
int loc_number;//考場號(hào)
int loc_rank;
}stu[30005];
/*
//The output must be sorted in nondecreasing order of the final ranks.
The testees with the same score must have the same rank, and the output
must be sorted in nondecreasing order of their registration numbers.
*/
bool cmp(student x,student y)//排序規(guī)則
{
if(x.score != y.score)
return x.score>y.score;
else
return strcmp(x.id,y.id)<0;
}
int main()
{
int n;
scanf("%d",&n);
int loc_sum=n;
int count=0;
while(n--)
{
int k;//各個(gè)考場人數(shù)
scanf("%d",&k);
// int count=0;//總數(shù)
for(int i=0;i<k;i++)//輸入學(xué)生信息
{
scanf("%s %d",stu[count].id, &stu[count].score);
stu[count].loc_number = (loc_sum-n);//賦值考場號(hào)
count++;
}
sort(stu+count-k,stu+count,cmp);
stu[count-k].loc_rank = 1;//初始化各個(gè)考場排名
for(int j=count-k+1;j<count;j++)//賦予排名
{
if(stu[j].score == stu[j-1].score)//如果與前一位考生同分
stu[j].loc_rank = stu[j-1].loc_rank;//排名也相同
else//不同分，排名為該考生前的人數(shù)
stu[j].loc_rank = j+1-(count-k);
}
}
//輸出要求
/*
For each test case, first print in one line the total number of testees.
Then print the final ranklist in the following format:
registration_number final_rank location_number local_rank
*/
printf("%d\n",count);//輸出所有考生人數(shù)total number
sort(stu,stu+count,cmp);//所有考生排序
int r = 1;//當(dāng)前考生排名
for(int i=0;i<count;i++)
{
if(i>0 && stu[i].score != stu[i-1].score)
r = i+1;
printf("%s ",stu[i].id);//registration_number
//location_number local_rank
printf("%d %d %d\n",r, stu[i].loc_number,stu[i].loc_rank);
}
return 0;
}
3、練習(xí)題
1923 Problem A 排序
來自 http://codeup.cn/contest.php?cid=100000581
題析：可以方便使用sort()函數(shù)
//1923ProblemA排序
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int arr[105];
int n;
while(scanf("%d",&n) != EOF)
{
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
sort(arr,arr+n);//sort()函數(shù)的使用
for(int i=0;i<n-1;i++)
printf("%d ",arr[i]);
printf("%d\n",arr[n-1]);
}
return 0;
}
1925 Problem B 特殊排序
來自 http://codeup.cn/contest.php?cid=100000581
//1925ProblemB特殊排序
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
int arr[1005];
int n;
while(scanf("%d",&n)!=EOF)//多點(diǎn)測試
{
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
sort(arr,arr+n);//排序函數(shù)
printf("%d ",arr[n-1]);
if(n==1)//特殊情況的處理
printf("%d\n",-1);
else
{
for(int i=0;i<n-1;i++)
{
printf("%d",arr[i]);
if(i<n-2)
printf(" ");
else
printf("\n");
}
}
}
return 0;
}
1926 Problem C EXCEL排序
來自 http://codeup.cn/contest.php?cid=100000581
題析：模擬+sort+學(xué)生結(jié)構(gòu)體 應(yīng)用，很經(jīng)典，字典序\同成績之類的處理,strcmp(x,y)當(dāng)x,y不相等時(shí)不為0，判斷視為true
//1926ProblemCEXCEL排序
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct student
{
char id[10];//學(xué)號(hào)
char name[10];//姓名
int grade;//成績
}stu[100005];
int c;
int cmp(student x,student y)
{
switch(c)
{//當(dāng)若干學(xué)生具有相同姓名或者相同成績時(shí)，則按他們的學(xué)號(hào)遞增排序。
case 1://按學(xué)號(hào)遞增排序
return strcmp(x.id,y.id)<0;break;//若str1=str2，則返回零；若str1<str2，則返回負(fù)數(shù)；若str1>str2，則返回正數(shù)
case 2://按姓名的非遞減字典序排序
if(!strcmp(x.name,y.name))
return strcmp(x.id,y.id)<0;
else
return strcmp(x.name,y.name)<0;
break;
case 3://按成績的非遞減排序
if(x.grade!=y.grade)
return x.grade<y.grade;
else
return strcmp(x.id,y.id)<0;
break;
default:
break;
}
/*
//當(dāng)若干學(xué)生具有相同姓名或者相同成績時(shí)，則按他們的學(xué)號(hào)遞增排序。
if(c==1)//按學(xué)號(hào)遞增排序
return strcmp(x.id,y.id)<0;//若str1=str2，則返回零；若str1<str2，則返回負(fù)數(shù)；若str1>str2，則返回正數(shù)
else if(c==2)//按姓名的非遞減字典序排序
{
if(!strcmp(x.name,y.name))
return strcmp(x.id,y.id)<0;
else
return strcmp(x.name,y.name)<0;
}
else if(c==3)//按成績的非遞減排序
{
if(x.grade!=y.grade)
return x.grade<y.grade;
else
return strcmp(x.id,y.id)<0;
}
*/
}
int main()
{
int n;
int count=1;
while(scanf("%d%d",&n,&c) != EOF && n!=0)
{
for(int i=0;i<n;i++)
{
scanf("%s %s %d",stu[i].id,stu[i].name,&stu[i].grade);
}
sort(stu,stu+n,cmp);
printf("Case %d:\n",count++);
for(int i=0;i<n;i++)
{
printf("%s %s %d\n",stu[i].id, stu[i].name, stu[i].grade);
}
}
return 0;
}
1927 Problem D 字符串內(nèi)排序
來自 http://codeup.cn/contest.php?cid=100000581
題析：gets()/puts()應(yīng)用，簡單應(yīng)用
//1927ProblemD字符串內(nèi)排序
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
char str[205];
while(gets(str)!=NULL)
{
int len = strlen(str);
sort(str,str+len);
// printf("%s\n",str);
puts(str);
}
return 0;
}
1978 Problem E Problem B
來自 http://codeup.cn/contest.php?cid=100000581
題析：注意數(shù)組下標(biāo)指針的意義，
隱含多點(diǎn)測試？？（單點(diǎn)測試錯(cuò)誤50%）
Sort()函數(shù)的應(yīng)用
//1978ProblemEProblem B
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int arr[15][15];
bool cmp(int x,int y)//從大到小的比較法則
{
return x>y;
}
int main()
{
int m;
while(scanf("%d",&m)!=EOF)//單點(diǎn)測試???
{
int sum_row[15]={0},sum_column[15]={0},sum_duijiao[2]={0};//行、列、對(duì)角和存儲(chǔ)矩陣
int sum[25]={0};//最終和存儲(chǔ)矩陣
int row_cnt=0,col_cnt=0,dj_cnt=0;//數(shù)組下標(biāo)指針
int sum_ce=0;
for(int i=0;i<m;i++)
{
for(int j=0;j<m;j++)
{
scanf("%d",&arr[i][j]);//輸入方陣數(shù)據(jù)
sum_row[i]+=arr[i][j]; //求每行的和
// cout<<sum_row[i]<<" ";
// cout<<endl;
if(i==j)
sum_duijiao[0]+=arr[i][j];//主對(duì)角線的和
if(i+j==m-1)
sum_duijiao[1]+=arr[i][j];//次對(duì)角線的和
sum_column[j] += arr[i][j];//求每列的和，對(duì)于列下標(biāo)j
// sum_column[int(j%(m-1))] += arr[i][j];//錯(cuò)誤做法，沒有搞清楚下標(biāo)的機(jī)制
}
// cout<<sum_column[i]<<" ";
// cout<<endl;
// sum_ce+=sum_row[i];
}
// cout<<sum_ce<<endl;
int k=0;//最終數(shù)組的下標(biāo)指針
//賦值轉(zhuǎn)移給最終數(shù)組
for(int i=0;i<m;i++)
{
sum[k++]=sum_row[i];
}
for(int i=0;i<m;i++)
{
sum[k++]=sum_column[i];
}
for(int i=0;i<2;i++)
{
sum[k++]=sum_duijiao[i];
}
sort(sum,sum+k,cmp);//排序
for(int i=0;i<k;i++)//輸出
{
printf("%d",sum[i]);
if(i<k-1)
printf(" ");
else
printf("\n");
}
}
return 0;
}
2043 Problem F 小白鼠排隊(duì)
來自 http://codeup.cn/contest.php?cid=100000581
題析：
struct{}arr[];結(jié)構(gòu)體、sort排序
注意結(jié)構(gòu)體的排序規(guī)則
//2043ProblemF小白鼠排隊(duì)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct mouse//老鼠結(jié)構(gòu)體
{
int weight;//體重
char color[15];//帽子顏色
}mou[105];
//bool cmp(int x,int y)//錯(cuò)誤
bool cmp(mouse x,mouse y)//正確排序規(guī)則
{
return x.weight>y.weight;
}
int main()
{
char color[105];
int N;
while(scanf("%d",&N) != EOF)//多點(diǎn)輸入
{
for(int i=0;i<N;i++)//輸入信息
scanf("%d%s",&mou[i].weight,mou[i].color);
sort(mou,mou+N,cmp);//排序
for(int i=0;i<N;i++)//輸出信息
printf("%s\n",mou[i].color);
// printf("\n");
}
return 0;
}
2069 Problem G 中位數(shù)
來自 http://codeup.cn/contest.php?cid=100000581
題析：
進(jìn)行模擬，得注意數(shù)組下標(biāo)的處理，從0開始與從1處理
從1開始的數(shù)組下標(biāo)有利于奇偶處理。
//2069ProblemG中位數(shù)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int num[10005];
int N;
while(scanf("%d",&N) != EOF && N!=0)//多點(diǎn)測試
{
// getchar();//消除換行符的影響
// memset(num,0,sizeof(num));//初始化數(shù)組，可有可無
int result;
for(int i=1;i<=N;i++)//注意下標(biāo)從1開始有助于下面處理
scanf("%d",&num[i]);
sort(num+1,num+N+1);//排序 ，上限為num+N+1,若為num+N，錯(cuò)誤50%
if(N%2==0)//偶數(shù)，中間兩個(gè)數(shù)
{
result = (num[N/2]+num[N/2+1])/2;
}
else//奇數(shù)，中間一個(gè)數(shù)
{
result = num[(N+1)/2];
}
printf("%d\n",result);
}
return 0;
}
2080 Problem H 整數(shù)奇偶排序
來自 http://codeup.cn/contest.php?cid=100000581
題析：
奇偶處理，sort()應(yīng)用，注意下標(biāo)初始化
多點(diǎn)測試的輸入形式
//2080ProblemH整數(shù)奇偶排序
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
bool cmp_even(int x,int y)
{
return x>y;
}
bool cmp_odd(int x,int y)
{
return x<y;
}
int main()
{
int num[15];
while(scanf("%d%d%d%d%d%d%d%d%d%d",&num[0],&num[1],&num[2],&num[3],&num[4],&num[5],&num[6],&num[7],&num[8],&num[9]) != EOF)
{
int even_cnt=0,odd_cnt=0,cnt=0;
int even[10]={0},odd[10]={0};
for(int i=0;i<10;i++)
{
if(num[i]%2==0)//偶數(shù)
odd[odd_cnt++]=num[i];
else//奇數(shù)
even[even_cnt++]=num[i];
}
sort(even,even+even_cnt,cmp_even);//奇數(shù)從大到小排序
for(int i=0;i<even_cnt;i++)//從大到小輸出奇數(shù)
printf("%d ",even[i]);
sort(odd,odd+odd_cnt,cmp_odd);//偶數(shù)排序
for(int i=0;i<odd_cnt-1;i++)//從小到大輸出偶數(shù)
printf("%d ",odd[i]);
printf("%d\n",odd[odd_cnt-1]);
}
return 0;
}
2088 Problem I 排名
來自 http://codeup.cn/contest.php?cid=100000581
題析：
M、N不分，題中許多注釋都是測試用的，因?yàn)镸、N搞混了，注意細(xì)節(jié)的處理
//2088ProblemI排名
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct student
{
char id[25];//準(zhǔn)考證號(hào)
int sol_p_n;//解決題目數(shù)
int p_id[15];//解決題目題號(hào)
int grade;//成績
}stu[1005];
bool cmp(student x,student y)
{
if(x.grade!=y.grade)
return x.grade>y.grade;
else
return strcmp(x.id,y.id)<0;
}
int main()
{
int N,M,G;
int course_grad[15]={0};
while(scanf("%d%d%d",&N,&M,&G) != EOF && N!=0)
{
int pass_cnt=0;
for(int i=1;i<=M;i++)//各科分?jǐn)?shù)
scanf("%d",&course_grad[i]);
// int count=0;
// cout<<M<<endl;
for(int i=0;i<N;i++)//輸入處理
{
stu[i].grade=0;
scanf("%s%d",&stu[i].id,&stu[i].sol_p_n);
// cout<<stu[i].sol_p_n<<endl;
for(int j=0;j<stu[i].sol_p_n;j++)//輸入解決的題
{
scanf("%d",&stu[i].p_id[j]);
stu[i].grade += course_grad[stu[i].p_id[j]];
// cout<<stu[i].grade<<endl;
}
if(stu[i].grade>=G)
pass_cnt++;
// cout<<pass_cnt<<endl;
// cout<<i<<endl;
// cout<<"46532"<<endl;
}
// cout<<"1312222"<<endl;
printf("%d\n",pass_cnt);
sort(stu,stu+N,cmp);
for(int i=0;i<N;i++)
{
if(stu[i].grade >= G)
printf("%s %d\n",stu[i].id,stu[i].grade);
}
}
return 0;
}
