[已解决]浇花问题

柿子饼同学

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

4 5
6 3
2 4
4 10
12 15

输出:

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  的最小区间宽度。
遍历所有满足条件的子区间，取其最小值即可

#include <stdio.h>
#include <stdlib.h>

int current_s(int* py,  int ns, int ne) {
        int max=py[ns], min=py[ns], i;
        for (i = ns; i <= ne; i++) {
                max = py[i] > max ? py[i] : max;
                min = py[i] < min ? py[i] : min;
        }
        return max - min;
}

int current_w(int* py, int *px, int ns, int ne, int s) {
        int t = current_s(py, ns, ne);
        return t >= s ? px[ne] - px[ns] > 0 ? px[ne] - px[ns] : px[ns] - px[ne] : -1;
}

int main(void) {
        int n = 0, s = 0, pot_width=-1, temp_w;
        scanf("%d %d", &n, &s);

        int* px = (int*)malloc(sizeof(int) * n);
        int* py = (int*)malloc(sizeof(int) * n);

        for (int i = 0; i < n; i++) {
                scanf("%d %d", px + i, py + i);
        }

        for (int x_left = 0; x_left < n; x_left++) {
                for (int x_right = 1; x_right < n; x_right++) {
                        temp_w = current_w(py, px, x_left, x_right, s);
                        if (temp_w != -1 && (pot_width == -1 || temp_w < pot_width) ) {
                                pot_width = temp_w;
                                //break;
                        }
                }
        }

        printf("最小花盆宽度: %d\n", pot_width);

        return 0;
}

柿子饼同学

风车呼呼呼 发表于 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