演算法 Activity Selection Problem

 avatar
user_6817964
c_cpp
2 years ago
1.2 kB
0
Indexable
Never
#include <stdio.h>
#define _CRT_SECIURE_NO_WARNINGS

int main()
{
    int n;
    scanf_s("%d", &n);
    int s[1000], f[1000], s_original[1000];

    for (int i = 1; i <= n; i++) {
        scanf_s("%d", &s[i]);
        s_original[i] = i;
    }
    for (int i = 1; i <= n; i++) {
        scanf_s("%d", &f[i]);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (s[j] > s[i]) {
                int temp = s[i];
                s[i] = s[j];
                s[j] = temp;
                temp = f[i];
                f[i] = f[j];
                f[j] = temp;
                temp = s_original[i];
                s_original[i] = s_original[j];
                s_original[j] = temp;
            }
        }
    }

    int get[100], total = 1;
    get[1] = n;
    for (int i = n - 1, j = n; i >= 1; i--) {
        if (f[i] <= s[j]) {
            total++;
            get[total] = i;
            j = i;
        }
    }


    printf("%d\n", total);



    printf("(%d", s_original[get[total]]);

    for (int i = total - 1; i >= 1; i--) {
        printf(",%d", s_original[get[i]]);
    }

    printf(")");
}