1035 插入与归并最后两个测试点无法通过+我有点没看懂“一轮”是怎么指代的

Question

1035 插入与归并最后两个测试点无法通过
这是我的代码

#include<stdio.h>
#define MAX 100

int mark=0;
void merge(int a[],int need[],int N,int start,int end){//归并
    int mid=start+(end-start)/2;
    int i=start,j=mid+1,k=0;
    int b[end-start+1];
    
    while(i<=mid&&j<=end){
        if(a[i]<a[j])
            b[k++]=a[i++];
        else
            b[k++]=a[j++];
    }
    while(i<=mid)
        b[k++]=a[i++];
    while(j<=end)
        b[k++]=a[j++];

    for(i=start,k=0;i<=end;i++,k++)
        a[i]=b[k];
}

int main(){
    int N;
    scanf("%d",&N);
    int init[MAX];
    int need[MAX];
    for(int i=0;i<N;i++)
        scanf("%d",&init[i]);
    for(int i=0;i<N;i++)
        scanf("%d",&need[i]);
    int i;//开始失序的位置1 2 3 7 8 5 9 4 6 0------>4

    for(i=0;i<N-1;i++){
        if(need[i]<=need[i+1])
            continue;
        else
            break;
    }
    int flag=0;//0-Insertion Sort;1-Merge Sort
    for(int j=i+1;j<N;j++){
        if(need[j]!=init[j]){
            flag=1;//是归并
            break;
        }
    }
    if(flag==0){//插入
        printf("Insertion Sort\n");
        if(i==N-1)//全部有序
            for(int j=0;j<N;j++){
                printf("%d",need[j]);
                if(j!=N-1)
                    printf(" ");
            }
        else{
            int temp=need[i+1];
            //printf("---%d\n",temp);
            for(int j=0;j<N;j++){
                if(need[j]>temp){//前面的都小于当前数
                    //printf("---%d\n",j);
                    for(int k=i;k>=j;k--){
                        need[k+1]=need[k];
                    }
                    need[j]=temp;
                    break;
                }
            }
            for(int j=0;j<N;j++){
                printf("%d",need[j]);
                if(j!=N-1)
                    printf(" ");
            }
        }
        
            
    }
    if(flag==1){//归并
        printf("Merge Sort\n");
        int len=2;
        while(len<=N){
            //int a[],int need[],int N,int start,int end
            for(int i=0;i<N;i+=len){
                if((i+len-1)>=N)//后面剩余的不足一组
                    merge(init,need,N,i,N-1);
                else
                    merge(init,need,N,i,i+len-1);
            }
            
            if(mark==1){//要输出的下一轮
                for(int k=0;k<N;k++){
                    printf("%d",init[k]);
                    if(k!=N-1)
                        printf(" ");
                }
                mark=2;
            }

            int match=1;
            for(int k=0;k<N;k++){
                if(need[k]!=init[k]){
                    match=0;
                    break;
                }
            }
            if(match)//跟给的数组完全匹配
                mark=1;
                
            if(mark==2) break;
            len*=2;//一组长度*2
        }
    }
}

我不是很明白题中的“一轮归并”是，指所有数都按新的分组完成排序，还是指可以在一个分组大小排序的过程中跟给出的序列匹配上。
就比如说：
10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6
这个最后的06是可以看做“9 4”->"4 9"排序完成后的下一组，因为"0 6"是组内有序的，所以下一轮还应该为“1 3 2 8 5 7 4 9 0 6”
还是“3 1 2 8 7 5 9 4 0 6"两两一组排序完成后得到的“1 3 2 8 5 7 4 9 0 6”，即下一组应该为“1 2 3 8 4 5 7 9 0 6”（下一轮就是4个为一组）
我是按后者写的（因为按照一样例无法通过），但请问剩下两个测试点是怎么弄呢

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

问题解答

你遇到了1035插入与归并排序算法的最后两个测试点无法通过的问题。根据你的代码，问题可能出在merge函数中。

在merge函数中，你使用了一个标志变量mark来记录当前的归并状态，但是你没有在每次归并完成后更新mark的值，这可能导致最后两个测试点无法通过。

建议你在merge函数中添加代码来更新mark的值，例如：

void merge(int a[]) {
    int i = 0, j = 0;
    while (i < MAX && j < MAX) {
        if (a[i] <= a[j]) {
            printf("%d ", a[i]);
            i++;
        } else {
            printf("%d ", a[j]);
            j++;
        }
        mark = i; // 更新mark的值
    }
    while (i < MAX) {
        printf("%d ", a[i]);
        i++;
    }
    printf("\n");
}

这样，在每次归并完成后，mark的值将被更新，从而解决最后两个测试点无法通过的问题。