求解贪心算法相关问题

Question

题目1： 已知X1,X2,X3,…,Xn是直线上的点，现希望用固定长度固定数量的木条去覆盖这些点，请编写程序求最多能够覆盖多少点？

输入要求：输入的第1行为三个整数n,m,k,分别表示直线上点的个数，木条的长度以及数量。输入的第2行有n个整数，表示坐标上的点。

输出要求：输出1行，为最多能够覆盖的点的个数。

输入样例：

8 3 2

10 7 6 1 -5 4 18 20

输出样例：

5

题目2：设n为一自然数，n可以分解成若干个不同的自然数的和，这样的分法有很多种，比如n=10, 10可以分解为：10=5+4+1; 10=5+3+2; 10+9+1; 10=8+2; 10=7+3; 10=6+4; 10=7+2+1; 10=6+3+1;…。在所有这些分法中，各加数乘积最大的为30, （10=5+3+2中加数的乘积为5*3*2=30）。试编写程序，求各种分解方法中各加数乘积的最大值。

输入要求：输入只有1行，自然数n。

输出要求：输出也只有1行，所有分解方法中各加数乘积的最大值。

题目3：有n个人参加一个马拉松接力游戏，游戏规定每个人可以根据自己的情况随时终止游戏并由下一个人继续接力。由于每个人的情况不同，即使同一个人也不可能在整个游戏过程中永远保持很好的状态。因此要求他们在比赛前根据每个人的情况需要制定一个接力规则，使整个比赛的时间越少越好。请编写程序帮助他们制定这样的接力方案。
输入要求：输入的第1行有三个整数n,k和m，分别表示参加接力的人的个数，每个人最多可以跑的公里数以及接力赛的距离（以公里为单位）。其后的n行，每行有k个整数，分别表示每个人跑整数1公里,2公里，….,K公里所花费的时间（以秒为单位，整数）。游戏要求每个人都必须参加比赛，且每次只能跑到整数公里后才能换人。
输出要求：输出1个整数,表示这些人跑完整个接力赛最少要花多少时间。

Answer 1

题目2, 仅供参考:

 #include<iostream>
#include<vector>
using namespace std;

class MaxProductNumber {
public:
    MaxProductNumber() :
            maxNum(0) {
    }
    ~MaxProductNumber() {
    }
    int getTmpMaxNum();
    int getMaxProductNumber() {
        return maxNum;
    }
    bool isExistAtVec(int val);
    void Solution(int n, int curValue, int num);

public:
    int maxNum;           //保存最大乘积
    vector<int> vec;     //保存每次获取的n的拆分数
};

bool MaxProductNumber::isExistAtVec(int val) {
    if (vec.size() <= 0) {
        return false;
    }

    for (int i = 0; i < vec.size(); ++i) {
        if (val == vec.at(i)) {
            return true;
        }
    }
    return false;
}

int MaxProductNumber::getTmpMaxNum() {
    int tmpMax = 1;
    for (int i = 0; i < vec.size(); i++) {
        tmpMax *= vec.at(i);
        cout << vec.at(i) << " ";
    }
    cout << endl;
    return tmpMax;
}

void MaxProductNumber::Solution(int n, int curValue, int num) {
    if (num == n) {
        int tmp = getTmpMaxNum();
        if (tmp > maxNum) {
            maxNum = tmp;
        }
        return;
    }
    for (int i = curValue; i < n; i++) {
        if (!isExistAtVec(i)) {
            num += i;
            vec.push_back(i);
            Solution(n, curValue + 1, num);
            vec.pop_back();
            num -= i;
        }
    }
}

int main() {
    int n = 0;
    cin >> n;
    MaxProductNumber maxProduct;
    maxProduct.Solution(n, 1, 0);
    cout << maxProduct.getMaxProductNumber() << endl;
    return 0;
}

题目3, 与题目2其实相同, 只不过是又加了一个限制条件, 题目3可以翻译为:
将m公里数分解: m = 1 + 2 + 3..., m=1 + 1 + 1 ..., m=1+1+2+2.., 从所有的分解结果中找出分解数q的个数满足条件: q <= n, 然后在看这组数是否都小于k,
符合所有条件, 最后就获取到了花费的时间, 然后从就可以找到最少的花费时间了.
举个例子:
n=3
k=3
m=4
1 3 4
2 3 5
1 2 3
那么m可以拆解为: 1 1 1 1, 2 2, 1 3, 符合条件q <= n的是 2, 2 和 1 3, 对于2, 2这种情况 派第3个人跑2公里, 派第1个或第2个跑两公里, 共花费5.
对于1, 3这种情况, 派第3个人跑3公里, 第一个人跑1公里, 共花费4
综合最少时间为4