Codeforces 853A Planning

简单贪心一下即可:从第k分钟开始,每一次都选择能起飞的飞机中代价最大的那个。

贪心选择性

设代价最大的飞机为i;假设:不选择i而选择了某个飞机j(cost[j] < cost[i]),最终得到了全局最优解,设为S。此时如果将j和i的位置调换,新的解将比S更优,即S不是全局最优解,与假设矛盾。因此,在某个全局最优解中,在当前这一步一定会选择i。

最优子结构

在选择了i之后,剩下的航班安排问题为子问题。在选择i之后所形成的全局最优解S中,这个子问题的解一定是该子问题的最优解。如果不是的话,则必然能够有某个更优的子问题的解,与i合并之后,将会得到一个更优的全局解。这与S是全局最优解矛盾。

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

struct tmp {
    int id;
    long long cost;
    int new_time;

    bool operator<(const tmp& rhs) const {
        return cost < rhs.cost;
    }
};

int main() {
    int n, k;
    cin >> n >> k;
    tmp* cost = new tmp[n];

    for (int i = 0; i < n; i++) {
        cost[i].id = i;
        cin >> cost[i].cost;
    }

    priority_queue<tmp> q;

    for (int i = 0; i < k; i++) {
        q.push(cost[i]);
    }

    long long int total_cost = 0;
    for (int i = k; i < n + k; i++) {
        if (i < n)
            q.push(cost[i]);
        tmp t = q.top();
        q.pop();
        cost[t.id].new_time = i + 1;
        total_cost += (i - t.id) * t.cost;
    }

    cout << total_cost << endl;

    for (int i = 0; i < n; i++) {
        if (i != 0)
            cout << " ";
        cout << cost[i].new_time;
    }
    cout << endl;

    delete[] cost;
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注