解题思路

这道题目需要我们在一个已经放置了若干物品的置物架上，找到放置新物品的最小移动成本。核心思路是检查所有可能的空隙和通过移动物品能创造的空隙，找到满足条件的最小移动次数。

具体步骤如下：

1. 检查现有空隙：首先遍历所有已存在物品之间的空隙，以及置物架两端的空隙，看是否有足够大的空间直接放置新物品。如果有，直接返回0。
2. 检查移动物品后的空隙：如果没有现成的足够大空隙，我们需要考虑移动连续的K个物品来创造空间。对于每个可能的连续K个物品的移动，计算移动后能获得的总空间（包括移动物品前后的空隙和物品之间的空隙），看是否能满足新物品的大小需求。
3. 寻找最小K：我们需要找到满足条件的最小K值。可以使用滑动窗口的方法来高效地检查所有可能的连续K个物品的移动情况。

算法选择上，这属于贪心算法的应用，我们试图在每一步找到局部最优解（最小的K值），最终得到全局最优解。

复杂度分析

• 时间复杂度：O(M)，其中M是已有物品的数量。我们需要遍历所有物品一次来检查现有空隙，然后使用滑动窗口检查所有可能的连续K个物品的移动情况。
• 空间复杂度：O(M)，用于存储已有物品的位置信息。在最坏情况下，我们需要存储所有物品的起始和结束位置。

代码实现

Python

def solve():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    K = int(input[ptr])
    ptr += 1
    
    items = []
    for _ in range(M):
        s = int(input[ptr])
        e = int(input[ptr+1])
        items.append((s, e))
        ptr += 2
    
    min_moves = float('inf')
    
    # 检查现有空隙
    # 检查最前面的空隙
    if items[0][0] >= K:
        print(0)
        return
    
    # 检查物品之间的空隙
    for i in range(M - 1):
        gap = items[i+1][0] - items[i][1]
        if gap >= K:
            print(0)
            return
    
    # 检查最后面的空隙
    if N - items[-1][1] >= K:
        print(0)
        return
    
    # 需要移动物品的情况
    # 使用滑动窗口找最小的K
    left = 0
    total_gap = 0
    
    for right in range(M):
        if right > 0:
            total_gap += items[right][0] - items[right-1][1]
        
        # 维护窗口大小，确保窗口内物品数量足够
        while left <= right and (right - left + 1) > 0:
            # 计算总可用空间
            # 前面的空隙
            front_gap = items[left][0] - (0 if left == 0 else items[left-1][1])
            # 后面的空隙
            back_gap = (N if right == M-1 else items[right+1][0]) - items[right][1]
            # 总空间
            total_space = front_gap + total_gap + back_gap
            
            if total_space >= K:
                min_moves = min(min_moves, right - left + 1)
                # 尝试缩小窗口
                if left < right:
                    total_gap -= items[left+1][0] - items[left][1]
                    left += 1
                else:
                    break
            else:
                break
    
    if min_moves != float('inf'):
        print(min_moves)
    else:
        print(-1)

solve()

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = br.readLine().split(" ");
        int N = Integer.parseInt(firstLine[0]);
        int M = Integer.parseInt(firstLine[1]);
        int K = Integer.parseInt(firstLine[2]);
        
        List<int[]> items = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            String[] line = br.readLine().split(" ");
            int s = Integer.parseInt(line[0]);
            int e = Integer.parseInt(line[1]);
            items.add(new int[]{s, e});
        }
        
        int minMoves = Integer.MAX_VALUE;
        
        // 检查现有空隙
        // 检查最前面的空隙
        if (items.get(0)[0] >= K) {
            System.out.println(0);
            return;
        }
        
        // 检查物品之间的空隙
        for (int i = 0; i < M - 1; i++) {
            int gap = items.get(i+1)[0] - items.get(i)[1];
            if (gap >= K) {
                System.out.println(0);
                return;
            }
        }
        
        // 检查最后面的空隙
        if (N - items.get(M-1)[1] >= K) {
            System.out.println(0);
            return;
        }
        
        // 需要移动物品的情况
        int left = 0;
        int totalGap = 0;
        
        for (int right = 0; right < M; right++) {
            if (right > 0) {
                totalGap += items.get(right)[0] - items.get(right-1)[1];
            }
            
            while (left <= right) {
                // 计算总可用空间
                int frontGap = items.get(left)[0] - (left == 0 ? 0 : items.get(left-1)[1]);
                int backGap = (right == M-1 ? N : items.get(right+1)[0]) - items.get(right)[1];
                int totalSpace = frontGap + totalGap + backGap;
                
                if (totalSpace >= K) {
                    minMoves = Math.min(minMoves, right - left + 1);
                    if (left < right) {
                        totalGap -= items.get(left+1)[0] - items.get(left)[1];
                        left++;
                    } else {
                        break;
                    }
                } else {
                    break;
                }
            }
        }
        
        if (minMoves != Integer.MAX_VALUE) {
            System.out.println(minMoves);
        } else {
            System.out.println(-1);
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M, K;
    cin >> N >> M >> K;
    
    vector<pair<int, int>> items;
    for (int i = 0; i < M; ++i) {
        int s, e;
        cin >> s >> e;
        items.emplace_back(s, e);
    }
    
    int min_moves = INT_MAX;
    
    // 检查现有空隙
    // 检查最前面的空隙
    if (items[0].first >= K) {
        cout << 0 << endl;
        return 0;
    }
    
    // 检查物品之间的空隙
    for (int i = 0; i < M - 1; ++i) {
        int gap = items[i+1].first - items[i].second;
        if (gap >= K) {
            cout << 0 << endl;
            return 0;
        }
    }
    
    // 检查最后面的空隙
    if (N - items.back().second >= K) {
        cout << 0 << endl;
        return 0;
    }
    
    // 需要移动物品的情况
    int left = 0;
    int total_gap = 0;
    
    for (int right = 0; right < M; ++right) {
        if (right > 0) {
            total_gap += items[right].first - items[right-1].second;
        }
        
        while (left <= right) {
            // 计算总可用空间
            int front_gap = items[left].first - (left == 0 ? 0 : items[left-1].second);
            int back_gap = (right == M-1 ? N : items[right+1].first) - items[right].second;
            int total_space = front_gap + total_gap + back_gap;
            
            if (total_space >= K) {
                min_moves = min(min_moves, right - left + 1);
                if (left < right) {
                    total_gap -= items[left+1].first - items[left].second;
                    ++left;
                } else {
                    break;
                }
            } else {
                break;
            }
        }
    }
    
    if (min_moves != INT_MAX) {
        cout << min_moves << endl;
    } else {
        cout << -1 << endl;
    }
    
    return 0;
}

题目内容

有一个长度为 $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

输入

10 3 5
3 4
6 8
9 10

输出

1

说明

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

样例2

输入

16 6 6
0 1
4 6
8 9
10 11
12 13
14 15

输出

2

说明

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

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