CCF 입문 P216 연습6: 엑스포 자원봉사자

5378 단어 문제풀이

문제풀이

#include 

void sortsubarray(int data[], int begin, int end) {
    int i, j, k, temp;
    for(i = begin; i < end; i++) {
        for(j = i - 1; j >= begin; j--) if(data[j] > data[i]) break;
        if(j != i - 1) {
            temp = data[i];
            for(k = i - 1; k > j; k--) {
                data[k + 1] = data[k];
            } 
            data[k + 1] = temp;
        }
    } 
}

void sort2array(int data1[], int data2[], int n) {
    int i, j, k, temp1, temp2;
    for(i = 1; i < n; i++) {
        for(j = i - 1; j >= 0; j--) if(data1[j] > data1[i]) break;
        if(j != i - 1) {
            temp1 = data1[i];
            temp2 = data2[i];
            for(k = i - 1; k > j; k--) {
                data1[k + 1] = data1[k];
                data2[k + 1] = data2[k];
            } 
            data1[k + 1] = temp1;
            data2[k + 1] = temp2;
        }
    } 
} 

void sortid(int data[], int id[], int n) {
    int i, j;
    for(i = 0; i < n; i++) {
        for(j = i; j < n; j++) if(data[j] != data[i]) break;
        j--;

        if(j == i) continue;
        sortsubarray(id, i, j);
    }
}

int main() {
    FILE *f = fopen("in.txt", "r");  

    int scoreline, n;
    fscanf(f, "%d%d", &n, &scoreline);
    int id[n + 5], score[n + 5];
    int i;
    for(i = 0; i < n; i++) {
        fscanf(f, "%d%d", &id[i], &score[i]);
    }
    fclose(f);

    scoreline *= 1.5;
    scoreline--;
    sort2array(score, id, n);
    sortid(score, id, n);

    for(i = scoreline; i < n; i++) if(score[i] != score[scoreline]) break;
    scoreline = i - 1;

    printf("%d %d
"
, score[scoreline], scoreline + 1); for(i = 0; i <= scoreline; i++) { printf("%d %d
"
, id[i], score[i]); } return 0; }

주의


이 문제 풀이 코드는 같은 경로에서 in을 입력합니다.txt 파일 입력이 문제의 해답은 결코 가장 좋은 해답이 아니다.

반성하다


두 개의 그룹을 동시에 정렬하고, 하위 그룹을 정렬하면 오류가 발생하기 쉽다.예컨대 본제 5, 6행
    for(i = begin; i < end; i++) {
        for(j = i - 1; j >= begin; j--) if(data[j] > data[i]) break;

하위 그룹의 시작 위치와 끝 위치 판단이 누락되어 id 그룹의 순서가 잘못될 확률이 높습니다.

지식점


정렬 삽입 정렬 알고리즘: 정렬 삽입(By KSkun).

좋은 웹페이지 즐겨찾기