为何用选择排序即AC,而用插入排序就0分呢?

P1093 [NOIP2007 普及组] 奖学金

Christophe_ @ 2020-07-17 15:38:35

以下是零分代码:

#include<cstdio>
#include<algorithm>
using namespace std;
int n,Total[100000],Chinese[100000],Number[100000];
int main(void){
    scanf("%d",&n);
    for(int i=2;i<=n+1;i++){
        int M,E;
        scanf("%d %d %d",&Chinese[i-1],&M,&E);
        Total[i-1]=Chinese[i-1]+M+E;
        Number[i-1]=i;
    }
    for(int i=2;i<=n;i++){
        for(int j=i;j>=1;j--){
            if(Total[j]>Total[j-1]||Total[j]==Total[j-1]&&Chinese[j]>Chinese[j-1]||Total[j]==Total[j-1]&&Chinese[j]==Chinese[j-1]&&Number[j]<Number[j-1]){
                swap(Total[j],Total[j-1]);
                swap(Chinese[j],Chinese[j-1]);
                swap(Number[j],Number[j-1]);
            }
            else{
                break;
            }
            }
        }
    for(int i=1;i<=5;i++){
        printf("%d %d\n",Number[i],Total[i]);
     }
     return 0;
}  

而改为选择排序之后:(AC代码)

#include<cstdio>
#include<algorithm>
using namespace std;
int n,Total[100000],Chinese[100000],Number[100000];
int main(void){
    scanf("%d",&n);
    for(int i=2;i<=n+1;i++){
        int M,E;
        scanf("%d %d %d",&Chinese[i-1],&M,&E);
        Total[i-1]=Chinese[i-1]+M+E;
        Number[i-1]=i-1;
    }
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
 if(Total[j]>Total[i]||Total[j]==Total[i]&&Chinese[j]>Chinese[i]||Total[j]==Total[i]&&Chinese[j]==Chinese[i]&&Number[j]<Number[i]){
                swap(Total[j],Total[i]);
                swap(Chinese[j],Chinese[i]);
                swap(Number[j],Number[i]);
            }
            }
        }
    for(int i=1;i<=5;i++){
        printf("%d %d\n",Number[i],Total[i]);
 }
     return 0;
} 

请问是为何?


by Schwarzkopf_Henkal @ 2020-07-17 15:48:52

通常来说这不是排序的问题,是你代码写假了的问题。


by 云浅知处 @ 2020-07-17 15:53:21

@【昴星团】 sort不好么


by zwuis @ 2020-07-17 18:15:20

@【昴星团】 第 14 行

for (int j = i; j >= 1; j--) {

要是 j = 1,下面那个 if 就会比较 Total[1]Total[0]。你可没用 Total[0] 记录数据。

要改为 j >= 2


by Christophe_ @ 2020-07-18 21:31:05

@zwuis 依旧0分WA


by zwuis @ 2020-07-19 16:52:36

@【昴星团】 还有错啊

第 11 行

Number[i - 1] = i;

i = 2,运行 Number[1] = 2;。有问题吧。

要改成 Number[i - 1] = i - 1; 吧。


by Christophe_ @ 2020-07-19 22:38:45

@zwuis 万分感谢,Accepted!


|