P3721.第2题-移动最少的物品

1000ms

Difficulty: 5

所属公司 : 华为

算法与标签>贪心算法

题目内容

有一个长度为 $N$ 的置物架，上面一级放置着 $M$ 个物品，每个物品大小不同，占用了置物架不同大小的长度空间，且物品之间不一定连续放置，可能存在空隙。现在你想放置你自己的物品，且希望在保持物品原有顺序的情况下，尽可能不去移动置物架上已存在的物品，即你的策略是：

1.如果存在足够的长度空间能放置你的物品，则直接放置你的物品，此时移动的物品数量为 $0$ ;

2.或者，你可以选择从 $i$ 号物品开始的连续 $K$ 个物品，将它们紧密排列，以获得空间，此时移动物品的数量为 $K$ ，同时你将获得 $K$ 个物品中间的空隙， $i$ 号物品向前的空隙，以及 $i+k$ 号物品向后的空隙，这三个空隙1的总和空间。

给你指定的长度、物品的排列，和你需要放置的物品大小，计算移动的物品数量的最小值。

输入描述

输入格式

1.输入为 $M +1$ 行

2.第一行包含三个数字: $N$ $M$ $K$ 。其中 $N$ 为置物架长度， $M$ 为已经存在的物品数量， $K$ 为需要放置的物品大小

3.第二行开始，每一行描述一个已经在置物架上的物品。每一行包含两个数字 $Si$ $Ei$ 。其中 $Si$ 代表物品的起始位置， $Ei$ 代表物品的结束位置。用例保证输入的物品顺序是从小到大排序的。

输入约束

1. $0＜N＜=5*10^5$

2. $0＜M＜=10^5$

3. $0＜=Si＜Ei＜=5*10^5$ ，即物品一定具有长度，且不会超过置物架

4.所有数据均为整数，多个物品之间不会重叠，由输入保证

输出描述

输出数字，代表移动的物品数量的最小值

如果找不到放置的空间，输出 $-1$

样例1

输入

输出

说明

只需要把 $[3,4)$ 物品移动到最前，则新排布为 $[0,1)、[6,8)、[9,10)$ ，则在区间 $[1,6)$ 存在大小为 $5$ 的空隙，可放入新物品

1、	移动前：
2、	丨丨···丨丨········丨丨
3、	0 3 4 6 8 10
4、
5、	移动后：
6、	丨···丨丨········丨丨
7、	0 1 6 8 10

样例2

输入

输出

说明

将位于 $[4,6)$ 位置的 $1$ 号物品和位于 $[8,9)$ 的 $2$ 号物品、和 $0$ 号物品紧密排列，则最新的物品排列如下图所示，可以获得大小为 $6$ 的空间，足够放置新的大小为 $5$ 的物品。

1、	移动前：
2、	丨···丨丨······丨丨···丨丨···丨丨···丨丨···丨丨
3、	0 1 4 6 8 9 10 11 12 13 14 15 1
4、	6
5、	移动后：
6、	丨···丨······丨···丨丨···丨丨···丨丨···丨丨
7、	0 1 3 4 10 11 12 13 14 15 16

虽然移动 $[8,9)、[10,11)、[12,13)、[14,15)$ 四个物品也可以获得足够的空间，但是需要移动更多的物品

1、	移动前：
2、	丨···丨丨······丨丨···丨丨···丨丨···丨丨···丨丨
3、	0 1 4 6 8 9 10 11 12 13 14 15 16
4、
5、	移动后：
6、	丨···丨丨······丨···丨···丨···丨···丨丨
7、	0 1 4 6 7 8 9 10 16

输入

预期输出（选填）

解题思路

P3721.第2题-移动最少的物品

题目内容

输入描述

输出描述

样例1

样例2

Status

Development

Support

About