题解 | #星港交通调度#

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

struct stop{
    int r, p, a;
}; // 停泊申请

class Solution {
public:
    int minEnergyCost(int f, int m, int n, vector<stop> rp) {
        if (f * m < n) return -1;
        sort(rp.begin(), rp.end(), [](const stop& a, const stop& b){
            return a.p > b.p;
        }); // 按船员人数 p 降序排列，先保证 p 大的尽量接近首选层
        vector<int> left(f, m); // 记录各层剩余泊位数，初始都为 m ，即所有泊位都是空闲状态
        int ans = 0; 
        for (int i = 0; i < n; i++) {
            rp[i].a = rp[i].r;
            while (left[rp[i].a - 1] == 0) rp[i].a--;
            // 注意下标从 0 开始，而层数从 1 开始，所以，rp[i].a 对应的层的剩余泊位数是 left[rp[i].a - 1]
            left[rp[i].a - 1]--;
            ans += rp[i].p * (2 + rp[i].r - rp[i].a);
        }
        return ans;
    }
};

int main() {
    int f, m, n;
    cin >> f >> m >> n;
    vector<stop> rp(n);  
    for (int i = 0; i < n; i++) 
        cin >> rp[i].r >> rp[i].p;
    Solution sol;
    cout << sol.minEnergyCost(f, m, n, rp);
}
// 64 位输出请用 printf("%lld")