OPJ1.10 01-04排序与结构体

OPJ1.10

01 谁考了第k名

使用的是选择排序 \(O(n^2)\)复杂度
用\(x=max\)来进行比较

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int m,n;
int numx[105];
double nums[105];
int main( ){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++){
        scanf("%d%lf",&numx[i],&nums[i]);
    }
    
    for(int i=1;i<=m;i++){
            double x=2147483647.000;
            int pos=0;
        for(int j=i;j<=m;j++){
            
            if(nums[j]<x){
                x=nums[j];
                pos=j;
            }
        //  printf("  i=%d  j=%d  pos=%d  x=%g\n",i,j,pos,x); 
        }
        swap(nums[i],nums[pos]);
        swap(numx[i],numx[pos]);
        //for(int z=1;z<=m;z++){
        //  printf("%d : %d %g\n",z,numx[z],nums[z]);
        //}
        
    }
    
    printf("%d %g",numx[m+1-n],nums[m+1-n]);
    return 0;
} 

02 奇数上升序列

使用快速排序 sort \(O(nlogn)\)

sort（a+1，a+n+1，cmp）

（如果不写cmp自动从小到大排序，到了后面有字典序的比较时必须写cmp）

//BMS AC
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
bool cmp(int x,int y){
    return x<y;
} 
int a[505],b[505];
int n=0,cnt=0;
char e[505];
int main( ){
    //memset(b,',',sizeof(b));
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1,cmp);
    int j=1;
    for(int i=1;i<=n;i++){
        if(a[i]%2!=0) b[j]=a[i],j++;
    }
    for(int i=1;i<=j-2;i++){
        printf("%d,",b[i]);
    }
    printf("%d",b[j-1]);
    return 0;
} 

插 快速排序和冒泡排序的模板

均为\(O(nlogn)\)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
bool cmp(int x,int y){
    return x>y;
}
int main( ){
    int n;
    int a[10001];
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1,cmp);
    //for(int i=1;i<=n;i++){
    //  for(int j=1;j<=n;j++){
    //      if(a[j]<a[j-1]) swap(a[j],a[j-1]);
    //  }
    //}注释的是冒泡排序
    for(int i=1;i<=n;i++){
        printf("%d ",a[i]);
    }
    
    return 0;
} 

（也许）可以对字符串进行sort排序，但是好像不分大小写（cmp可能没写好）

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int a[100005];

int main(){
    int n;
    scanf("%d",&n);
    char a[n+2];
    scanf("%s",a+1);
    sort(a+1,a+n+1);
    //for(int i=1;i<=n;i++){
        printf("%s",a+1);
    //}
    return 0;
}

03 成绩排序

A 没有结构体的写法

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int m,n;
char numx[105];
int nums[105];
int main( ){
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%c%d",numx[i],&nums[i]);
    }
    //记录名字 
    for(int i=1;i<=m;i++){
            int x=2147483647.000;
            int pos=0;
        for(int j=i;j<=m;j++){
            if(nums[j]<x){
                x=nums[j];
                pos=j;
            }
        //  printf("  i=%d  j=%d  pos=%d  x=%g\n",i,j,pos,x); 
        }
        swap(nums[i],nums[pos]);
        swap(numx[i],numx[pos]);
        //for(int z=1;z<=m;z++){
        //  printf("%d : %d %g\n",z,numx[z],nums[z]);
        //}
        
    }
    for(int z=1;z<=m;z++){
        printf("%d %g\n",numx[z],nums[z]);
    }
    //printf("%d %g",numx[m+1-n],nums[m+1-n]);
    return 0;
} 

B 使用结构体的写法

注意cmp的写法
~~~
//AC

include

include

include

using namespace std;
struct name{
char a[22];
int b;
};
name g[22];
int n;
bool cmp(name x,name y){
if(x.b==y.b) return strcmp(x.a,y.a)<0;
else return x.b>y.b;
}
int main( ){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",g[i].a);
scanf("%d",&g[i].b);
}
sort(g+1,g+n+1,cmp);
for(int i=1;i<=n;i++){
printf("%s %d\n",g[i].a,g[i].b);
}
return 0;
}
~~~

04 奖学金

在排序的时候有多种要求要在cmp中声明
bool类型
~~~

include

include

include

using namespace std;
struct student{
int chinese;
int english;
int maths;
int total;
int number;
};
student s[605];
bool cmp(student a,student b){
if(a.total==b.total&&a.chinese==b.chinese) return a.number<b.number;
if(a.total==b.total&&a.chinese!=b.chinese) return a.chinese>b.chinese;
if(a.total!=b.total) return a.total>b.total;
}
int n;
int main( ){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&s[i].chinese,&s[i].maths,&s[i].english);
s[i].number=i;
s[i].total=s[i].chinese+s[i].english+s[i].maths;
}
sort(s+1,s+n+1,cmp);
for(int i=1;i<=5;i++){
printf("%d %d\n",s[i].number,s[i].total);
}
return 0;
}
~~~

Openjudge 1.10 01-04排序与结构体

原文：https://www.cnblogs.com/liuziwen0224/p/11992373.html