您的位置: 首页  >  文章  >  PAT1085，运行超时

PAT1085，运行超时

分类: 文章 • 2023-11-22 12:38:04


写的过程中遇到了许多问题，至今还没解决，首先这个是我的c语言代码，运行超时

#include<stdio.h>

#include<malloc.h>
#include<string.h>
typedef struct student{
char school[7];
int score;
int people;
}*STU,stu;
int Bi_Jiao(STU A, int  **num, int f, int p);
void Q_Sort(STU A, int  **num, int L,int R);
void Translate_Name(char *A);
int Find_Same(char *A, char *co);
int Get_Score(char *A, int sco);
int main()
{
int n = 0;// 学校数量
int N; // 学生人数
    int is_find = 0;
    scanf("%d",&N);           // 是否找到相同学校标记，找到置1
// 暂时保存录入的学生信息
char sch[7]; // 考生学校
char id[7];  // 考生学号
int sco;    // 考生成绩
int i, k, j;
    STU A = (STU) malloc(N*sizeof(stu));
// 以下为录入学生信息


for ( i = 0; i < N; ++i) {
        is_find = 0;
scanf("%s",id);
scanf("%d",&sco);
scanf("%s",sch);
sco = Get_Score(id, sco);    // 分数转换
Translate_Name(sch);         // 学校名转换成小写
for (k = 0; k < n; ++k){     // 找是否有相同的学校
if (Find_Same(A[k].school, sch)) {
A[k].people++;       // 人数加一
  A[k].score += sco;   // 分数整合
is_find = 1;         // 找到学校置1
break;
}
}
if (!is_find) {    // 如果没有找到
   for(j = 0;sch[j] != '\0';++j)
                A[k].school[j] = sch[j]; // 初始化学校
            A[k].school[j] = '\0';
A[k].people = 1;   // 初始化学校考生数
A[k].score = sco;  // 初始化分数
n++;               // 更新总学校数
}
}
// 以上为录入学生信息
int **num = (int **)malloc(2*sizeof(int *)); // 用来存储学校的排名与下表信息，排序只交换数组下标
num[0] = (int *)malloc(n*sizeof(int));
num[1] = (int *)malloc(n*sizeof(int));
for ( i = 0; i < n; ++i) {
num[0][i] = i;     // 存储学校数组下标
num[1][i] = i + 1; // 存储学校名次
}
Q_Sort(A ,num ,0 ,n-1 ); // 把数据进行排序
printf("%d\n",n);
for ( i = 1; i < n; ++i) {
if (A[num[0][i]].score == A[num[0][i - 1]].score) {
num[1][i] = num[1][i - 1];
}
}
for ( i = 0; i < n; ++i) {
            printf("%d %s %d %d\n", num[1][i],A[num[0][i]].school,A[num[0][i]].score,A[num[0][i]].people );
// cout << num[1][i] << " " << A[num[0][i]].school << " " << A[num[0][i]].score << " " << A[num[0][i]].people << endl;
}
free(num[0]);
free(num[1]);
free(num);
free(A);
    return 0;
}
// 分数转化
int Get_Score(char *A, int sco)
{
if ('T' == A[0])
return (sco * 1.5);
else if ('B' == A[0])
return (sco / 1.5);
else
return sco;
}
// 查找是否有相同的学校
int Find_Same(char *A, char  *co)
{
int i;
for(i = 0; A[i] != '\0' && co[i] != '\0';++i)
        if(A[i] != co[i])
            return 0;
    if(A[i] == '\0' && co[i] == '\0')
        return 1;
    return 0;
}
// 把学校名翻译成小写
void Translate_Name(char *A)
{
    int i;
for ( i = 0; A[i] != '\0'; ++i)
if (A[i] < 'a')
A[i] += 32;
}
// 快速排序：因为来回交换数据太过麻烦，所以我交换了数据对应的下标，并且用数组num存储
void Q_Sort(STU A, int **num, int L,int R)
{
if (L < R) {
int temp = num[0][L]; // 把待排数组第一个元素拿出
int l = L;
int r = R;
while (l < r) {       // l < r 循环
while (l < r && Bi_Jiao(A,num, r,temp))
r--;
if(l < r)
  num[0][l++] = num[0][r];
while (l < r && !Bi_Jiao(A, num,l , temp))
l++;
if(l < r)
num[0][r--] = num[0][l];
}
num[0][l] = temp;
Q_Sort(A, num, L,l-1 ); // 左边排序
Q_Sort(A, num, l+1, R); // 右边排序
}
}
 // 确定两个元素的大小关系
int  Bi_Jiao(STU A, int **num, int f, int p)
{
if (A[num[0][f]].score < A[p].score)
return 1;
else if ((A[num[0][f]].score == A[p].score) && (A[num[0][f]].people > A[p].people))
return 1;
else if ((A[num[0][f]].score == A[p].score) && (A[num[0][f]].people == A[p].people) && (strcmp(A[num[0][f]].school,A[p].school) > 0) )
return 1;
else
return 0;

}


提交结果运行超时

PAT1085，运行超时


下面是我之前用C++写的，也是出现了运行超时的问题，刚开始我用的是冒泡排序，运行超时；看了百度的解释说冒泡排序不行，然后自己写了一个快速排序，但是还是运行超时

#include<iostream>
#include<string>
using namespace std;
typedef struct student{
string school;
int score;
int people;
}*STU,stu;
bool Bi_Jiao(STU A, int ** &num, int f, int p);
void Q_Sort(STU A, int ** &num, int L,int R);
void Translate_Name(string &A);
bool Find_Same(string A, string co);
int Get_Score(string A, int sco);
int main()
{
int n = 0;// 学校数量
int N; // 学生人数 
cin >> N;
STU A = new stu[N];
// 暂时保存录入的学生信息
string sch; // 考生学校
string id;  // 考生学号
int sco;    // 考生成绩
// 以下为录入学生信息
for (int i = 0,k; i < N; ++i) {
cin >> id; 
cin >> sco;
cin >> sch;
sco = Get_Score(id, sco);    // 分数转换
Translate_Name(sch);         // 学校名转换成小写
int is_find = 0;             // 是否找到相同学校标记，找到置1
for (k = 0; k < n; ++k){     // 找是否有相同的学校
if (Find_Same(A[k].school, sch)) {  
A[k].people++;       // 人数加一
  A[k].score += sco;   // 分数整合
is_find = 1;         // 找到学校置1
break;
}
}
if (!is_find) {        // 如果没有找到
A[k].school = sch; // 初始化学校
A[k].people = 1;   // 初始化学校考生数
A[k].score = sco;  // 初始化分数
n++;               // 更新总学校数
}
}
// 以上为录入学生信息
int **num = new int*[2]; // 用来存储学校的排名与下表信息，排序只交换数组下标
num[0] = new int[n];
num[1] = new int[n];
for (int i = 0; i < n; ++i) {
num[0][i] = i;     // 存储学校数组下标
num[1][i] = i + 1; // 存储学校名次
}
Q_Sort(A ,num ,0 ,n-1 ); // 把数据进行排序
cout << n << endl;
for (int i = 1; i < n; ++i) {
if (A[num[0][i]].score == A[num[0][i - 1]].score) {
num[1][i] = num[1][i - 1];
}
}
for (int i = 0; i < n; ++i) {
cout << num[1][i] << " " << A[num[0][i]].school << " " << A[num[0][i]].score << " " << A[num[0][i]].people << endl;
}
delete [] num[0];
delete [] num[1];
delete [] num;
delete [] A;
    return 0;
}
int Get_Score(string A, int sco)
{
if ('T' == A[0])
return (sco * 1.5);
else if ('B' == A[0])
return (sco / 1.5);
else
return sco;
}
bool Find_Same(string A, string co)
{
if (A == co)
return true;
else
return false;
}
void Translate_Name(string &A)
{
for (int i = 0; A[i] != '\0'; ++i)
if (A[i] < 'a')
A[i] += 32;
}
void Q_Sort(STU A, int ** &num, int L,int R)
{
if (L < R) {
int temp = num[0][L]; // 把待排数组第一个元素拿出
int l = L;
int r = R;
while (l < r) {       // l < r 循环
while (l < r && Bi_Jiao(A,num, r,temp))
r--;
if(l < r)
  num[0][l++] = num[0][r];
while (l < r && !Bi_Jiao(A, num,l , temp))
l++;
if(l < r)
num[0][r--] = num[0][l];
}
num[0][l] = temp;    
Q_Sort(A, num, L,l-1 ); // 左边排序
Q_Sort(A, num, l+1, R); // 右边排序


}
}
bool Bi_Jiao(STU A, int ** &num, int f, int p)
{
if (A[num[0][f]].score < A[p].score)
return true;
else if ((A[num[0][f]].score == A[p].score) && (A[num[0][f]].people > A[p].people))
return true;
else if ((A[num[0][f]].score == A[p].score) && (A[num[0][f]].people == A[p].people) && (A[num[0][f]].school > A[p].school))
return true;
else
return false;
}

PAT1085，运行超时


急求大佬能帮帮忙！！！


相关推荐