第三个贪心

A – 汽车加油问题

#include <bits/stdc++.h>
using namespace std;
int a[5010], n, k;

signed main()
{
    cin >> n >> k;
    for (int i = 0; i <= k; i++)
        cin >> a[i];

    for (int i = 0; i <= k; i++)
        if (a[i] > n)
            return cout << "No Solution!", 0;

    int now = 0, ans = 0;
    for (int i = k; i >= 0; i--)
    {
        now += a[i];
        if (now > n)
            ans++, now = a[i];
    }
    cout << ans << endl;
}

B – 多元Huffman编码问题

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a.begin(), a.end());
    int sum = a[n - 1] + a[n - 2];
    int ans = a[n - 1] + a[n - 2];
    for (int i = n - 3; i >= 0; i--)
        ans += sum + a[i], sum += a[i];
    cout << ans << " ", ans = 0;

    priority_queue<int, vector<int>, greater<int>> que;
    for (int i = 0; i < n; i++)
        que.push(a[i]);
    while (que.size() % (k - 1) != 1)
        que.push(0);

    while (que.size() > k)
    {
        sum = 0;
        for (int j = 0; j < k; j++)
            sum += que.top(), que.pop();

        ans += sum;
        que.push(sum);
    }
    while (que.size())
        ans += que.top(), que.pop();

    cout << ans << endl;
}

E – 最优合并问题

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a.begin(), a.end());
    int ans = 0, sum = a[n - 1];
    for (int i = n - 2; i >= 0; i--)
        sum += a[i], ans += sum;

    cout << ans - n + 1 << " ";
    ans = 0, sum = a[0];
    priority_queue<int, vector<int>, greater<int>> que;
    for (int i = 0; i < n; i++)
        que.push(a[i]);
    while (que.size() > 1)
    {
        int a = que.top();
        que.pop();
        int b = que.top();
        que.pop();
        que.push(a + b);
        ans += a + b;
    }
    cout << ans - n + 1;
}

F – 区间覆盖问题

#include <bits/stdc++.h>
using namespace std;

signed main()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a.begin(), a.end());

    int now = a[0] + k, ans = 1;
    for (int i = 0; i < n; i++)
        if (a[i] > now)
            now = a[i] + k, ans++;

    cout << ans << endl;
}

原文地址：http://www.cnblogs.com/zzh1206/p/16820781.html