# CF853A Planning

• 24通过
• 46提交
• 题目来源
• 评测方式 RemoteJudge
• 标签 排序 线段树 贪心
• 难度 提高+/省选-
• 时空限制 1000ms / 512MB
• 提示：收藏到任务计划后，可在首页查看。

## 题意翻译

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

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

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

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

输入格式：

输入数据的第一行包括两个整数n和k(1<=k<=n<=300000)。

第二行包括n个整数c1，c2，...，cn(1<=ci<=10^7).

输出格式：

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

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

说明：

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

## 题目描述

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 $c_{i}$ burles. Help her find the order for flights to depart in the new schedule that minimizes the total cost for the airport.

## 输入输出格式

输入格式：

The first line contains two integers $n$ and $k$ ( $1<=k<=n<=300000$ ), 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 $c_{1},c_{2},...,c_{n}$ ( $1<=c_{i}<=10^{7}$ ), here $c_{i}$ is the cost of delaying the $i$ -th flight for one minute.

输出格式：

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

The second line must contain $n$ different integers $t_{1},t_{2},...,t_{n}$ ( $k+1<=t_{i}<=k+n$ ), here $t_{i}$ is the minute when the $i$ -th flight must depart. If there are several optimal schedules, print any of them.

## 输入输出样例

输入样例#1： 复制
5 2
4 2 1 10 2

输出样例#1： 复制
20
3 6 7 4 5


## 说明

Let us consider sample test. If Helen just moves all flights $2$ minutes later preserving the order, the total cost of delaying the flights would be $(3-1)·4+(4-2)·2+(5-3)·1+(6-4)·10+(7-5)·2=38$ burles.

However, the better schedule is shown in the sample answer, its cost is $(3-1)·4+(6-2)·2+(7-3)·1+(4-4)·10+(5-5)·2=20$ burles.

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。