https://codeforces.com/problemset/problem/1786/B
2024.12.22 工作室训练赛J题

蛋糕问题

描述：
一个面包店的蛋糕装配线需要优化，一次制作n个蛋糕。每个蛋糕都需要被覆盖上巧克力。

具体设定：

1. 传送带可以看作一个数轴
2. 第i个蛋糕占据区间[ai-w, ai+w]，这些区间互不重叠
3. 上方有n个巧克力分配器，第i个分配器覆盖区间[bi-h, bi+h]，这些区间互不重叠
4. 按钮只能按一次，所有分配器同时工作
5. 可以移动传送带，但蛋糕的相对位置不变

目标：
判断是否可以通过移动传送带，使每个蛋糕都能被巧克力完全覆盖，且不会有巧克力洒在蛋糕外。

输入格式：

第一行：测试用例数量t (1 ≤ t ≤ 10^5)
每个测试用例包含：
    第一行：三个整数n,w,h (1 ≤ n ≤ 10^5; 1 ≤ w,h ≤ 10^5; h ≤ w)
    第二行：n个整数a1,a2,...,an (1 ≤ ai ≤ 10^9)
    第三行：n个整数b1,b2,...,bn (1 ≤ bi ≤ 10^9)

条件保证：

• 所有测试用例中n的总和不超过10^5
• 蛋糕区间互不重叠：ai+w < ai+1-w
• 分配器区间互不重叠：bi+h < bi+1-h

输出格式：
对每个测试用例输出一行：

• 如果可以实现要求，输出"YES"
• 否则输出"NO"
  （大小写不敏感）

样例：

输入：
4
3 10 5
65 95 165
40 65 145
5 2 1
1 6 11 16 21
4 9 14 19 24
3 3 2
13 22 29
5 16 25
4 4 1
27 36 127 136
35 50 141 144

输出：
YES
YES
NO
YES

具体设定

1. 传送带可以看作一个数轴

• 第i个蛋糕占据区间[ai-w, ai+w]，这些区间互不重叠
• 上方有n个巧克力分配器，第i个分配器覆盖区间[bi-h, bi+h]，这些区间互不重叠
• 按钮只能按一次，所有分配器同时工作
• 可以移动传送带，但蛋糕的相对位置不变

目标

判断是否可以通过移动传送带，使每个蛋糕都能被巧克力完全覆盖，且不会有巧克力洒在蛋糕外。

解题思路

1. 问题分析

• 每个蛋糕有固定宽度2w
• 每个分配器有固定覆盖宽度2h
• 需要找到一个合适的传送带位置，使所有蛋糕都能被对应的分配器完全覆盖

2. 核心思路

• 对于每对蛋糕和分配器，计算：

  • left：分配器左边界与蛋糕左边界的相对位置
  • right：分配器右边界与蛋糕右边界的相对位置l
  • 如果存在可行解，则必须满足：-left ≤ right

• 计算每对蛋糕和分配器的left和right值，

  • 取所有left值的最小值和right值的最小值
  • 最后判断-left是否小于等于right

  • -left是因为需要向左边位移，需要和right统一向量方向

• 关键是理解：

  • 问题的本质是找一个公共的移动距离
  • 每个蛋糕都对这个移动距离提出了一个范围要求
  • 计算所有蛋糕的最小允许位移范围
  • 所有范围的交集就是可行

3. 具体实现

#include <stdio.h>
#include <limits.h>
#define For(x) for(int i=0;i<x;i++)
#define ll long long
ll min(ll a,ll b) {return a > b ? b:a;}
void scanf_array(int *arr,int len){For(len) scanf("%d",arr+i);}
void solve();
int main(){
    int t;
    scanf("%d",&t);
    For(t) solve();
}
void solve(){
    int n,w,h;
    //w=d_cake，h=d_coo
    scanf("%d%d%d",&n,&w,&h);
    int cakes[n],coos[n];
    scanf_array(cakes,n);
    scanf_array(coos,n);
    ll left=LLONG_MAX,right=LLONG_MAX;
    For(n){
        left=min(left,(coos[i]-h)-(cakes[i]-w));
        right=min(right,(cakes[i]+w)-(coos[i]+h));
    }
    // printf("[%3lld,%3lld] ",left,right);
    printf((-left)>right ? "no\n":"yes\n");
}

示例分析

输入：

1
3 10 5
65 95 165 // 蛋糕位置
40 65 145 // 分配器位置

1. 第一对(蛋糕1-分配器1)

• 蛋糕1: [55, 75] (65±10)

• 分配器1: [35, 45] (40±5)

  • left1 = 35 - 55 = -20
  • right1 = 75 - 45 = 30

2. 第二对(蛋糕2-分配器2)

• 蛋糕2: [85, 105] (95±10)

• 分配器2: [60, 70] (65±5)

  • left2 = 60 - 85 = -25
  • right2 = 105 - 70 = 35

3. 第三对(蛋糕3-分配器3)

• 蛋糕3: [155, 175] (165±10)

• 分配器3: [140, 150] (145±5)

  • left3 = 140 - 155 = -15
  • right3 = 175 - 150 = 25

最终结果

• left = min(-20, -25, -15) = -25
• right = min(30, 35, 25) = 25
• -left = 25，right = 25
• (-left)>right 不成立
• 因此输出: "yes"