贪心是一种很重要的算法思想，下列问题中不适合用贪心解决的是（ ）。 A.田忌和齐王赛马，他们各有n匹马，一共要进行n场比赛，每匹马只能出场一次，赢的一方从输的一方获得200银币，打平就不得钱。问田忌要怎样安排马的出场次序才能使最后获得的钱最多？ B.给定一个十进制正整数n（0<n<100000000），每个数位上的数字均不为0，n的位数为m，现在从m位中删除k位，求生成的新整数最小为多少。 C.给定一个长度为m的区间，再给出n条线段的起点和终点，求最少使用多少条线段可以将整个区间完全覆盖。 D.有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

B.给定一个十进制正整数n（0<n<100000000），每个数位上的数字均不为0，n的位数为m，现在从m位中删除k位，求生成的新整数最小为多少。 这个问题不适合用贪心解决，因为每一位的数字大小不仅与该位的数字有关，还与其他位的数字有关，无法通过每一位的最优解得到整个问题的最优解。需要通过其他算法思想来解决，比如动态规划。

相关问题

贪心算法解决田忌赛马问题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;
}

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

田忌赛马贪心算法java

田忌赛马是一个经典的中国策略游戏，故事中田忌通过调整马的出场顺序，利用每个马的速度优势战胜了齐威王。在贪心算法中，我们可以借鉴这个思想来解决问题。贪心法是一种每一步都采取当前状态下最好或最优的选择，希望这样的局部最优解最终会导向全局最优解。

在Java中实现田忌赛马贪心算法，通常会定义三个等级的马（例如A、B、C），每次比赛选择最有可能赢得对手最低等级的马出战。以下是简单的步骤：

1. 定义三个马的胜率数组或列表，表示各自对阵其他等级马的胜率。
2. 对于每场比赛，从田忌的马中选出胜率最高的马对齐威王最差的马。
3. 遍历所有比赛，记录田忌的总胜场数。

这里是一个简化版的Java代码示例：

class Horse {
    public int speed; // 马的速度
}

public class TianJi {
    private static final int NUM_OF_RACES = 3;

    public static void main(String[] args) {
        Horse[] tianJiHorses = {new Horse(), new Horse(), new Horse()}; // 田忌的马
        Horse[] weiWangHorses = {new Horse(), new Horse(), new Horse()}; // 齐威王的马

        // 假设胜率已知并填充到speed属性中
        // ...

        int wins = solveTianji(tianJiHorses, weiWangHorses);
        System.out.println("田忌赢得了 " + wins + " 场比赛");
    }

    private static int solveTianji(Horse[] tianJiHorses, Horse[] weiWangHorses) {
        int tianjiWins = 0;
        for (int i = 0; i < NUM_OF_RACES; i++) {
            if (tianJiHorses[i].speed > weiWangHorses[i].speed) {
                tianjiWins++;
            }
        }
        return tianjiWins;
    }
}