二分算法、贪心思想实现优化

Question

题目描述
David 作为一名 scut 的大学生，自然需要去学习。
在 scut，有 N 门不同的课程，一个学期一共有 M 周，对于每一周，会上 N 次课，每一门课程恰好一周上一次课，David 对于每一个课程都有一个熟练度，初始时都为 0。
对于一节课 David 可以选择如下选项中的一个：
去上课：如果他上的是第 i 门课，那么他对于这节课的熟练度增加 Ai。
翘课：David 热爱学习，所以他会选一门课自学，如果他选了第 i 门课，那么他对于这节课的熟练度增加 Bi。
为了去更多的学习课外知识，David 不会在课下学习这 N 门课程，但是他又不想要让自己挂科，于是他找到了你，他想让自己对每一门课的熟练度的最小值最大。
输入格式
第一行两个整数 N,M
接下来一行 N 个整数 Ai。
接下来一行 N 个整数 Bi。
输出格式
仅输出一行一个整数表示你的答案。
样例数据
输入
3 3
19 4 5
2 6 2
输出
18

Answer 1

是c还是java

#include <stdio.h>
#include <stdlib.h>

// 比较函数，用于快速排序
int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int main() {
    int N, M;
    scanf("%d %d", &N, &M);

    int* A = (int*)malloc(N * sizeof(int));
    int* B = (int*)malloc(N * sizeof(int));

    for (int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }

    for (int i = 0; i < N; i++) {
        scanf("%d", &B[i]);
    }

    // 按照课程 i 的 B[i] - A[i] 从大到小排序
    // 这样选择翘课时优先选择 B[i] 大的课程
    // 避免使用贪心思想时选择导致最小值最大的方案
    int* diff = (int*)malloc(N * sizeof(int));
    for (int i = 0; i < N; i++) {
        diff[i] = B[i] - A[i];
    }
    qsort(diff, N, sizeof(int), cmp);

    // 统计一共有多少个正数和负数
    int positive = 0, negative = 0;
    for (int i = 0; i < N; i++) {
        if (diff[i] > 0) {
            positive++;
        }
        else if (diff[i] < 0) {
            negative++;
        }
    }

    // 选择使得熟练度最小的方案
    int minSkill = 0;
    if (positive <= M) {
        // 如果正数的个数小于等于 M
        // 那么可以选择所有正数，剩下的 M - positive 个位置选择差值最小的负数
        for (int i = 0; i < positive; i++) {
            minSkill += A[i];
        }
        for (int i = positive; i < N; i++) {
            minSkill += B[i];
        }
        if (M > positive) {
            qsort(A, N, sizeof(int), cmp); // 将 A 数组重新排序

            for (int i = 0; i < M - positive; i++) {
                minSkill += A[i];
            }
        }
    }
    else {
        // 如果正数的个数大于 M
        // 那么只能选择使得差值最小的前 M 个正数
        for (int i = 0; i < M; i++) {
            minSkill += A[i];
        }
    }

    free(A);
    free(B);
    free(diff);

    printf("%d\n", minSkill/2);

    return 0;
}