＃PAT＃day10

Introduction （2）—— The algorithm is preliminary （4.4 greedy ）

1067 Sort with Swap(0, i)

My code （19/25）

#include<stdio.h>
//#include<algorithm>
//using namespace std;

int a[100010];

void swap(int &a,int &b){
    
    int temp=a;
    a=b;
    b=temp;
}
int main(){
    
    int n,change=0,flag=-1,pos_0,pos_x,t=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
    
        scanf("%d",&a[i]);
        if(a[i]==0) pos_0=i;
    }
    while(flag==-1){
    
        if(a[0]!=0){
    
            for(pos_x=0;pos_x<n;pos_x++){
    
                if(a[pos_x]==pos_0) break;
            }
            swap(a[pos_0],a[pos_x]);
            pos_0=pos_x;
            change++;
        }
        else if(a[0]==0){
    
            for(t++;t<n;t++){
    
                if(a[t]!=t){
    
                    swap(a[0],a[t]);
                    pos_0=t;
                    change++;
                    break;
                }
            }
            if(t==n) flag=1;// Orderly 
        }
    }
    printf("%d",change);
}

notes

1. The reason for running timeout is that the time complexity is too high . I fixed the position and moved the element , So every time I look for if(a[pos_x]==pos_0) Need to be for loop . You can actually fix elements , Subscript with elements , And the storage location , So every time I look if(a[pos_x]==pos_0) No need for loop , And can directly locate ！（ Thinking is too fixed ）
   

Modified code

#include<stdio.h>
//#include<algorithm>
//using namespace std;

int a[100010];
//int a[100];

void swap(int &a,int &b){
    
    int temp=a;
    a=b;
    b=temp;
}
int main(){
    
    int n,change=0,flag=-1,t=0,temp;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
    
        scanf("%d",&temp);
        a[temp]=i;
        //if(temp==0) pos_0=i;
    }
    while(flag==-1){
    
        if(a[0]!=0){
    

            swap(a[0],a[a[0]]);
            //pos_0=pos_x;
            change++;
        }
        else if(a[0]==0){
    
            for(t++;t<n;t++){
    
                if(a[t]!=t){
    
                    swap(a[0],a[t]);
                    //pos_0=t;
                    change++;
                    break;
                }
            }
            if(t==n) flag=1;// Orderly 
        }
    }
    printf("%d",change);
}

1038 Recover the Smallest Number

My code

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

struct Segment{
    
    char it[17];
}segment[10010];
//

bool cmp(Segment a,Segment b){
    
    strcat(a.it,b.it);
    strcat(b.it,a.it);
    return strcmp(a.it,b.it)<0;
}

int main(){
    
    int n,total=0;
    scanf("%d",&n);
    while(n--){
    
        char temp[9];
        scanf("%s",temp);
        int len_temp=strlen(temp),flag=-1;
        for(int i=0;i<len_temp;i++){
    
            if(temp[i]!='0'){
    
                flag=1;
                break;
            }
        }
        if(flag==1){
    
            strcpy(segment[total++].it,temp);
        }
    }
    if(total==0) printf("0\n");
    else{
    
        sort(segment,segment+total,cmp);
        int len0=strlen(segment[0].it);
        int first_no_zero;
        for(first_no_zero=0;first_no_zero<len0;first_no_zero++){
    
            if(segment[0].it[first_no_zero]!='0'){
    
                break;
            }
        }
        for(int i=first_no_zero;i<len0;i++){
    
            printf("%c",segment[0].it[i]);
        }
        for(int i=1;i<total;i++){
    
            printf("%s",segment[i].it);
        }
    }
    
}

notes

1. At first I didn't notice if all the inputs were ’000’ character string , Then the output should have a ’0’, This boundary situation .
2. However, the last test point still failed after the modification ：
   
3. This problem uses a standard template library STL Inside string The type will be better , Maybe the first 6 One test point can pass .