💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🌻 听说本周PDD的笔试要开咯，作为笔试最难的互联网大厂之一，题目还是有挑战性的

🍭 本次给大家带来 2023 PDD校招的笔试题，加油一起备战PDD秋招

🍉 01.K小姐的西瓜摆放问题

问题描述

K小姐家里有一个很长的走廊，她想在走廊上摆放一些西瓜。走廊可以看作一条数轴，一共有 个可以摆放西瓜的位置，第 个位置的坐标为 。K小姐准备了 个西瓜，第 个西瓜的直径为 。

K小姐想把西瓜摆放在走廊上，一个西瓜可以摆放在任意一个位置，也可以横着摆放。如果一个西瓜横着摆放在位置 ，那么它会占据区间 ；如果一个西瓜竖着摆放在位置 ，那么它只会占据位置 。

摆放西瓜需要满足以下条件：

1. 每个西瓜要么横着摆放，要么竖着摆放；
2. 任意两个西瓜之间不能有重叠部分，即它们占据的区间不能有交集；
3. 每个位置至多只能摆放一个西瓜。

K小姐想知道，在满足上述条件的情况下，最多可以摆放多少个西瓜。

输入格式

第一行包含一个正整数 ，表示可以摆放西瓜的位置数量。

接下来 行，每行包含两个正整数 和 ，分别表示第 个位置的坐标和第 个西瓜的直径。

输出格式

输出一个整数，表示最多可以摆放的西瓜数量。

样例输入

3
1 2
3 2
5 2

样例输出

2

数据范围

题解

本题可以使用动态规划来解决。

定义状态 表示前 个位置中，第 个西瓜横着摆放/竖着摆放/不摆放西瓜时的最大摆放数量。

对于第 个位置，我们有以下几种状态转移：

1. 如果第 个西瓜横着摆放，那么它的左端点为 ，右端点为 。我们需要找到满足条件的前一个位置 ，使得 。此时有 。

2. 如果第 个西瓜竖着摆放，那么它只占据位置 。我们需要找到满足条件的前一个位置 ，使得 。此时有 。

3. 如果第 个位置不摆放西瓜，那么 。

最后的答案即为 。

时间复杂度 ，空间复杂度 。

参考代码

• Python

def solve(n, x, d):
    dp = [[0] * 3 for _ in range(n+1)]
    
    for i in range(1, n+1):
        dp[i][0] = dp[i][1] = dp[i][2] = 0
        
        for j in range(i-1, -1, -1):
            if x[i-1] - d[i-1]/2 > x[j-1] + d[j-1]/2:
                dp[i][0] = max(dp[i][0], max(dp[j][0], dp[j][1], dp[j][2]) + 1)
                break
                
        for j in range(i-1, -1, -1):
            if x[i-1] > x[j-1] + d[j-1]/2:
                dp[i][1] = max(dp[i][1], max(dp[j][0], dp[j][1], dp[j][2]) + 1)
                break
                
        dp[i][2] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2])
        
    return max(dp[n][0], dp[n][1], dp[n][2])

n = int(input())
x, d = [], []
for _ in range(n):
    xi, di = map(int, input().split())
    x.append(xi)
    d.append(di)

print(solve(n, x, d))

• Java

import java.util.*;

public class Solution {
    public static int solve(int n, int[] x, int[] d) {
        int[][] dp = new int[n+1][3];
        
        for (int i = 1; i <= n; i++) {
            dp[i][0] = dp[i][1] = dp[i][2] = 0;
            
            for (int j = i-1; j >= 0; j--) {
                if (x[i-1] - d[i-1]/2.0 > x[j-1] + d[j-1]/2.0) {
                    dp[i][0] = Math.max(dp[i][0], Math.max(dp[j][0], Math.max(dp[j][1], dp[j][2])) + 1);
                    break;
                }
            }
            
            for (int j = i-1; j >= 0; j--) {
                if (x[i-1] > x[j-1] + d[j-1]/2.0) {
                    dp[i][1] = Math.max(dp[i][1], Math.max(dp[j][0], Math.max(dp[j][1], dp[j][2])) + 1);
                    break;
                }
            }
            
            dp[i][2] = Math.max(dp[i-1][0], Math.max(dp[i-1][1], dp[i-1][2]));
        }
        
        return Math.max(dp[n][0], Math.max(dp[n][1], dp[n][2]));
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] x = new int[n];
        int[] d = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
            d[i] = sc.nextInt();
        }
        System.out.println(solve(n, x, d));
    }
}

• Cpp

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

int solve(int n, vector<int>& x, vector<int>& d) {
    vector<vector<int>> dp(n+1, vector<int>(3, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int j = i-1; j >= 0; j--) {
            if (x[i-1] - d[i-1]/2.0 > x[j-1] + d[j-1]/2.0) {
                dp[i][0] = max(dp[i][0], max(dp[j][0], max(dp[j][1], dp[j][2])) + 1);
                break;
            }
        }
        
        for (int j = i-1; j >= 0; j--) {
            if (x[i-1] > x[j-1] + d[j-1]/2.0) {
                dp[i][1] = max(dp[i][1], max(dp[j][0], max(dp[j][1], dp[j][2])) + 1);
                break;
            }
        }
        
        dp[i][2] = max(dp[i-1][0], max(dp[i-1][1], dp[i-1][2]));
    }
    
    return max(dp[n][0], max(dp[n][1], dp[n][2]));
}

int main() {
    int n;
    cin >> n;
    vector<int> x(n), d(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> d[i]