#433 - C. Planning（贪心，优先队列）

落日映苍穹つ 2022-06-08 05:20 202阅读 0赞

--------------------

题目连接：[http://codeforces.com/contest/854/problem/C][http_codeforces.com_contest_854_problem_C]

## 题目描述 ##

### Description ###

Helen works in Metropolis airport. She is responsible for creating a departure schedule. There are n flights that must depart today, the i-th of them is planned to depart at the i-th minute of the day.

Metropolis airport is the main transport hub of Metropolia, so it is difficult to keep the schedule intact. This is exactly the case today: because of technical issues, no flights were able to depart during the first k minutes of the day, so now the new departure schedule must be created.

All n scheduled flights must now depart at different minutes between (k + 1)-th and (k + n)-th, inclusive. However, it’s not mandatory for the flights to depart in the same order they were initially scheduled to do so — their order in the new schedule can be different. There is only one restriction: no flight is allowed to depart earlier than it was supposed to depart in the initial schedule.

Helen knows that each minute of delay of the i-th flight costs airport ci burles. Help her find the order for flights to depart in the new schedule that minimizes the total cost for the airport.

### Input ###

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 300 000), here n is the number of flights, and k is the number of minutes in the beginning of the day that the flights did not depart.

The second line contains n integers c1, c2, …, cn (1 ≤ ci ≤ 107), here ci is the cost of delaying the i-th flight for one minute.

### Output ###

The first line must contain the minimum possible total cost of delaying the flights.

The second line must contain n different integers t1, t2, …, tn (k + 1 ≤ ti ≤ k + n), here ti is the minute when the i-th flight must depart. If there are several optimal schedules, print any of them.

### Sample Input ###

5 2  
4 2 1 10 2

### Sample Output ###

20  
3 6 7 4 5

## 解题思路 ##

题意：飞机要起飞，但是要延误K分钟，一共n架飞机  
下面有n个数 第i个数为第i分钟开始每秒损失n\[i\]金钱，例如4 2 1 10 2，第一分钟开始损失4金钱/分钟，第二分钟，第一架和第二架一共损失6金钱/分钟（都没起飞的情况下）  
明白了题意就好办了，做一个优先队列，就是带排序的队列，int回爆，用long long

## AC代码 ##

#include<iostream>
    #include<queue>
    #define MAXN 1000010
    
    using namespace std;
    
    struct node {
        int id, cost;
    // node(int id, int cost):id(id), cost(cost) {};
        bool operator < (const node& n) const { //让队列排序 
            return cost < n.cost;
        }
    }cnt[MAXN];
    
    int main() {
        long long n, k; 
        cin >> n >> k;
        priority_queue<node> q;
        long long sum = 0;
        for(long long i = 1; i <= n; i++) {
            cin >> cnt[i].cost;
            cnt[i].id = i;
        } 
        for(long long i = 1; i <= k; i++) q.push(cnt[i]); //把延时的时候可以起飞的飞机放进队列 
        for(long long i = k+1; i <= n+k; i++) {
            if(i <= n) {
                q.push(cnt[i]);//要一个一个放进去，因为不能在本来起飞的时间前起飞 
            }
            node val = q.top();
            q.pop();
            sum += (long long) (i - val.id) * val.cost;//只要优先起飞花费最多的飞机一定是花费最少的 
            cnt[val.id].id = i;
        }
        cout << sum << endl;
        for(long long i = 1; i <= n; i++) {
            cout << cnt[i].id << " ";//这里没哟要求输出格式 
        }
        return 0;
    }

[http_codeforces.com_contest_854_problem_C]: http://codeforces.com/contest/854/problem/C