渊子赛马 C语言 贪心算法

渊子赛马问题是一个经典的贪心算法问题。问题描述如下：有n匹马和m条赛道，每条赛道有一个难度系数，每匹马有一个能力值。每匹马只能参加难度系数不超过自己能力值的赛道，每条赛道只能有一匹马参加。请问最多有多少匹马能够参加比赛？

解决这个问题的贪心策略是：对于每匹马，选择能够参加的最难的赛道。这样可以保证每条赛道都有一匹能力最强的马参加，同时也能够让更多的马参加比赛。

具体实现方法是：首先将所有马按照能力值从大到小排序，然后依次遍历每匹马，对于每匹马，从难度系数不超过它能力值的赛道中选择难度系数最大的赛道，如果该赛道还没有被选择，则选择该赛道，否则继续选择下一个难度系数小于该马能力值的赛道，直到找到一个未被选择的赛道或者所有赛道都被选择了。

时间复杂度为O(nlogn+mlogm)。

相关问题

田忌赛马贪心算法c语言

田忌赛马问题是一个经典的贪心算法问题。下面是一个使用C语言实现的简单示例代码：

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

#define NUM_HORSES 10

int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int main() {
    int ti[NUM_HORSES] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};   // 田忌的马
    int qi[NUM_HORSES] = {8, 9, 10, 1, 2, 3, 4, 5, 6, 7};   // 齐王的马
    int ti_win = 0, qi_win = 0;  // 记录胜利次数
    int ti_idx = 0, qi_idx = 0;  // 田忌和齐王当前选手的位置

    qsort(ti, NUM_HORSES, sizeof(int), cmp);
    qsort(qi, NUM_HORSES, sizeof(int), cmp);

    while (ti_idx < NUM_HORSES && qi_idx < NUM_HORSES) {
        if (ti[ti_idx] > qi[qi_idx]) {   // 田忌的马跑得快
            ti_win++;
            ti_idx++;
            qi_idx++;
        } else {   // 齐王的马跑得快
            qi_win++;
            ti_idx++;
            qi_idx++;
        }
    }

    printf("田忌赢了%d场，齐王赢了%d场\n", ti_win, qi_win);
    return 0;
}

在这个示例代码中，我们先定义了田忌和齐王的马的速度，并将它们分别按照速度从小到大排序。然后，我们使用两个指针 ti_idx 和 qi_idx 来记录当前选手的位置，同时使用 ti_win 和 qi_win 来记录胜利场次。接着，我们在一个 while 循环中，不断比较当前两个选手的马的速度，以此来确定谁胜谁负。最后，输出田忌和齐王的胜利场次即可。

贪心算法解决田忌赛马问题C语言代码

以下是贪心算法解决田忌赛马问题的C语言代码：

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

#define MAX_N 100

int n;
int ta[MAX_N], tb[MAX_N];

int cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &ta[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &tb[i]);
    }

    qsort(ta, n, sizeof(int), cmp);
    qsort(tb, n, sizeof(int), cmp);

    int ans = 0;
    int j = 0;
    for (int i = 0; i < n; i++) {
        if (ta[i] > tb[j]) {
            ans++;
            j++;
        }
    }

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

    return 0;
}

该代码中，首先读入输入数据，然后将田忌和齐王的马按照速度从小到大排序。接着，使用贪心算法，从田忌的最慢的马开始比较，如果田忌的马速度大于齐王的马速度，则选择该马进行比赛，并将齐王的马的下标加一，直到比较完所有的马。最后输出比赛的场次即可。