【题解】Planning(起飞计划)

题目描述

Helen在大都会机场工作，她的任务是安排每天的航班起飞时刻。今天一共有n架飞机将要起飞，第i架飞机将在第i分钟起飞。

大都会机场是大都会最重要的交通枢纽，因此想要原封不动地按照起飞时刻表的时刻起飞是很困难的。今天的情况也是如此：由于技术原因，在今天一开始的k分钟内飞机不允许起飞，因此必须创建一个新的起飞时刻表。

所有的航班必须在第(k+1)分钟到第(k+n)分钟内(包括两端)起飞，而且每分钟仅能有一架飞机起飞。然而，航班起飞的先后顺序可以与最初的时刻表排好的顺序不同，重排的时刻表只有一个限制：飞机不能比它在初始时刻表中起飞的时刻还要早的时刻起飞(即：第i架飞机必须在第i分钟后或第i分钟时起飞)。

Helen知道第i架飞机起飞时刻每延误一分钟机场所需支付的额外花费cic_ici​是多少。帮助她找到额外花费最小的方案。

输入格式

输入数据的第一行包括两个整数n和k(1<=k<=n<=300000)，n为飞机数量，k是飞机不允许起飞的时间。

第二行包括n个整数c1，c2，...，cnc_1，c_2，...，c_nc1​，c2​，...，cn​(1<=ci<=1071<=c_i<=10^71<=ci​<=107). cic_ici​ 是第i架飞机起飞每延误一分钟机场所需支付的额外花费。

输出格式

输出数据的第一行包括一个整数，表示最小额外花费。

第二行包括n个整数t1，t2，...，tn(k+1<=ti<=k+n)t_1，t_2，...，t_n(k+1<=ti<=k+n)t1​，t2​，...，tn​(k+1<=ti<=k+n)，tit_iti​表示第i架家航班起飞的时刻。如果同时存在多种方案，输出任意一种。

样例 #1

样例输入 #1

5 2
4 2 1 10 2

样例输出 #1

20
3 6 7 4 5

提示

在样例中，如果Helen仅把每架飞机的起飞时刻都推迟2分钟，那么总额外花费是38。 但是，对于最佳结果来说，总额外花费为20。

(3−1)⋅4+(6−2)⋅2+(7−3)⋅1+(4−4)⋅10+(5−5)⋅2=20(3-1)·4+(6-2)·2+(7-3)·1+(4-4)·10+(5-5)·2=20(3−1)⋅4+(6−2)⋅2+(7−3)⋅1+(4−4)⋅10+(5−5)⋅2=20 burles.

题目分析

阅读题目可知题目要求的是最小的额外花费及航班的安排情况。核心在于求出怎样安排飞机航班，能使得额外花费最小。

额外花费是由每架飞机的每分钟的赔偿金×\times× 延误时间 累加得到。那么根据生活常识，必定是赔的高的越早起飞越好。

题目中要求飞机不能比它在初始时刻表中起飞的时刻还要早的时刻起飞，所以对于可以起飞的时刻，从剩余未安排的飞机中优先让赔偿金多的起飞。

剩余未安排的飞机是随着时间流失和安排航班会不断变化的，且每次都是找一个“最值”，这样一个找不断变化的最值过程，可以使用优先队列来实现它，将赔偿金多的设置为优先级较高。

struct node{
	int t,val;//原计划起飞时间、赔偿金
	friend bool operator <(node a,node b){//每秒赔偿高的优先级高
		return a.val<b.val;
	}
};

代码实现

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int N=3e5+5;
typedef long long ll;
int n,k;
int c[N];
struct node{
	int t,val;
	friend bool operator <(node a,node b){//每秒赔偿高的优先级高
		return a.val<b.val;
	}
};
priority_queue<node> q;
ll ans=0;
int ord[N];
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>c[i];
		q.push(node{i,c[i]});//飞机入队
		if(i<=k) continue;//飞机不得早于原定航班起飞 
		node cur=q.top();q.pop();//当前赔偿最高的优先起飞
		ans+=cur.val*(1LL*i-cur.t);//计算赔偿金额。注意相乘可能超int
		ord[cur.t]=i;//记录飞机的起飞时间
	}
	for(int i=n+1;i<=n+k;i++){//安排后k架次的起飞顺序
		node cur=q.top();q.pop();//赔偿多的先起飞
		ans+=cur.val*(1LL*i-cur.t);
		ord[cur.t]=i;
	}
	cout<<ans<<endl;//输出总和
	for(int i=1;i<=n;i++){//输出各架次的起飞时间
		cout<<ord[i]<<" ";
	}
	return 0;
}

Q.E.D.