题解 | #食品#

#include <bits/stdc++.h>

// 贪心 !

using namespace std;

typedef long long ll;


struct Node {
    int pos;
    ll val;
    bool operator <(const Node& node) const {
        return val == node.val ? pos > node.pos : val < node.val;
    }

    Node(int _pos, ll _val): pos(_pos), val(_val) {}

};

// 在每次出队列的时候,计算消耗! 
// 之前是抛出后 重新一次将队列元素加一次消耗,会超时!

int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> c(n + 1);
    for (int i = 1; i <= n; i++) cin >> c[i];

    // 把 前 m 个商品 放到大顶堆中!
    priority_queue<Node> q;

    ll cost = 0;

    // m 天的时间已经消耗的存储成本!
    for (int i = 1; i <= m; i++) {
        q.push(Node(i, c[i])); // 单天成本最高的,最顶上呆着!
    }


    for (int i = m + 1; i <= n; i++) { // 每天生产新的后,直接入队列!
        q.push(Node(i, c[i]));

        Node top = q.top();

        q.pop(); // 卖掉单天储藏成本最高的!

        cost += top.val * (i - top.pos);
    }

    int cur = n;

    while (!q.empty()) {
        ++cur;
        Node top = q.top();
        q.pop();
        cost += top.val * (cur - top.pos);
    }

    cout << cost << endl;
    return 0;

}