CF853A Planning

    • 24通过
    • 46提交
  • 题目来源 CodeForces 853A
  • 评测方式 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。

    感谢@radish布団 提供的翻译

    题目描述

    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类违反进行处理。