TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4312
  • 题目
  • P4312飞行管制
    限制 : 时间限制 : - MS   空间限制 : 265536 KB
    评测说明 : 1s
    问题描述

    何老板管理着一个非常繁忙的机场,该机场只有一条起飞跑道,所以每分钟最多只能一架飞机起飞。今天有n(编号1到n)架航班将起飞离港。按原定计划,第i架飞机将在第i分钟起飞。但突然的暴雨天气使得飞行计划被延误了。暴雨持续了k分钟,也就是在第1到第k分钟这段时间飞机无法起飞。
        所有n架飞机只能被安排在[k+1,k+n]这段时间内起飞。现在需要你来帮忙调整飞行时间表。要求每分钟安排一架飞机起飞,但是飞机的起飞时间不能早于原先安排的起飞时间。同时,因为飞机的大小和飞行距离的不同,不同飞机因延迟起飞产生的费用可能不同,其中i号飞机每延误一分钟将损失Ci块钱。

    何老板想知道,安排怎样的起飞顺序才能使得损失的总费用最少,请你计算出这个最小总费用。

    输入格式

    第一行,两个整数n和k

    第二行,n个空格间隔的整数,依次表示每架飞机延迟产生的费用,其中第i个数字表示i号飞机的延迟费用Ci。

    输出格式

    一个整数,最少损失的总费用。

    样例输入 1

    5 2
    4 2 1 10 2

    样例输出 1

    20

    样例输入 2

    6 4
    85666 52319 21890 51912 90704 10358

    样例输出 2

    1070345

    提示

    20%的數據滿足1≤ k ≤ n ≤100

    100%的數據滿足1 ≤ k ≤ n ≤ 300000。  0<=ci<=30000