[已解决]浇花问题

柿子饼同学

本题的思路好像是枚举左端点, 二分右端点, 但是不知道具体代码怎么写, 求帮助
样例输入:

1. 4 5
   
2. 6 3
   
3. 2 4
   
4. 4 10
   
5. 12 15

复制代码

输出:

1. 2

复制代码

最佳答案

月排行榜 / 总排行榜

风车呼呼呼

2022-7-7 12:42:07

柿子饼同学 发表于 2022-7-7 09:22
谢谢回答
current_s 就是求 [ns, ne] 区间内雨点的最大插值对吗
然后 15 行有点看不懂 , 为什么要用 px ...

是的，current_s是计算区间的差值，用于和 s 比较判断是否满足条件。
px[ne] - px[ns] 是区间宽度，也就是花盆宽度，为了适应输入的数据并不会刻意以x递增顺序排列，也就是 px[ne] 可能比 px[ns] 小，做一个判断区分是返回 px[ne] - px[ns] 还是返回它的相反数，亦或是不满足条件返回 -1。基于同样的理由，在main函数的循环中，我将break注释掉，这样才能保证坐标乱序输入情况下的结果正确性

跳转到最佳答案楼层

风车呼呼呼

转换为数学问题要好理解的多，即：对于一副散点图，区间内最大值与最小值之差 >= s  的最小区间宽度。
遍历所有满足条件的子区间，取其最小值即可

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int current_s(int* py,  int ns, int ne) {
   
5.         int max=py[ns], min=py[ns], i;
   
6.         for (i = ns; i <= ne; i++) {
   
7.                 max = py[i] > max ? py[i] : max;
   
8.                 min = py[i] < min ? py[i] : min;
   
9.         }
   
10.         return max - min;
    
11. }
    
12. 
    
13. int current_w(int* py, int *px, int ns, int ne, int s) {
    
14.         int t = current_s(py, ns, ne);
    
15.         return t >= s ? px[ne] - px[ns] > 0 ? px[ne] - px[ns] : px[ns] - px[ne] : -1;
    
16. }
    
17. 
    
18. int main(void) {
    
19.         int n = 0, s = 0, pot_width=-1, temp_w;
    
20.         scanf("%d %d", &n, &s);
    
21. 
    
22.         int* px = (int*)malloc(sizeof(int) * n);
    
23.         int* py = (int*)malloc(sizeof(int) * n);
    
24. 
    
25.         for (int i = 0; i < n; i++) {
    
26.                 scanf("%d %d", px + i, py + i);
    
27.         }
    
28. 
    
29.         for (int x_left = 0; x_left < n; x_left++) {
    
30.                 for (int x_right = 1; x_right < n; x_right++) {
    
31.                         temp_w = current_w(py, px, x_left, x_right, s);
    
32.                         if (temp_w != -1 && (pot_width == -1 || temp_w < pot_width) ) {
    
33.                                 pot_width = temp_w;
    
34.                                 //break;
    
35.                         }
    
36.                 }
    
37.         }
    
38. 
    
39.         printf("最小花盆宽度: %d\n", pot_width);
    
40. 
    
41.         return 0;
    
42. }

复制代码

柿子饼同学

风车呼呼呼 发表于 2022-7-6 14:26
转换为数学问题要好理解的多，即：对于一副散点图，区间内最大值与最小值之差 >= s  的最小区间宽度。
遍 ...

谢谢回答
current_s 就是求 [ns, ne] 区间内雨点的最大插值对吗
然后 15 行有点看不懂 , 为什么要用 px[ne] - px[ns] , 这不是每个雨点的坐标吗
有什么关系

风车呼呼呼

柿子饼同学 发表于 2022-7-7 09:22
谢谢回答
current_s 就是求 [ns, ne] 区间内雨点的最大插值对吗
然后 15 行有点看不懂 , 为什么要用 px ...

是的，current_s是计算区间的差值，用于和 s 比较判断是否满足条件。
px[ne] - px[ns] 是区间宽度，也就是花盆宽度，为了适应输入的数据并不会刻意以x递增顺序排列，也就是 px[ne] 可能比 px[ns] 小，做一个判断区分是返回 px[ne] - px[ns] 还是返回它的相反数，亦或是不满足条件返回 -1。基于同样的理由，在main函数的循环中，我将break注释掉，这样才能保证坐标乱序输入情况下的结果正确性

柿子饼同学

风车呼呼呼 发表于 2022-7-7 12:42
是的，current_s是计算区间的差值，用于和 s 比较判断是否满足条件。
px[ne] - px[ns] 是区间宽度，也就 ...

ok , 懂了

hornwong