浇花问题
本题的思路好像是枚举左端点, 二分右端点, 但是不知道具体代码怎么写, 求帮助样例输入:4 5
6 3
2 4
4 10
12 15
输出:2 本帖最后由 风车呼呼呼 于 2022-7-6 14:28 编辑
转换为数学问题要好理解的多，即：对于一副散点图，区间内最大值与最小值之差 >= s的最小区间宽度。
遍历所有满足条件的子区间，取其最小值即可
#include <stdio.h>
#include <stdlib.h>
int current_s(int* py,int ns, int ne) {
int max=py, min=py, i;
for (i = ns; i <= ne; i++) {
max = py > max ? py : max;
min = py < min ? py : 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 - px > 0 ? px - px : px - px : -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 就是求 区间内雨点的最大插值对吗
然后 15 行有点看不懂 , 为什么要用 px - px , 这不是每个雨点的坐标吗
有什么关系
柿子饼同学 发表于 2022-7-7 09:22
谢谢回答
current_s 就是求 区间内雨点的最大插值对吗
然后 15 行有点看不懂 , 为什么要用 px ...
是的，current_s是计算区间的差值，用于和 s 比较判断是否满足条件。
px - px 是区间宽度，也就是花盆宽度，为了适应输入的数据并不会刻意以x递增顺序排列，也就是 px 可能比 px 小，做一个判断区分是返回 px - px 还是返回它的相反数，亦或是不满足条件返回 -1。基于同样的理由，在main函数的循环中，我将break注释掉，这样才能保证坐标乱序输入情况下的结果正确性 风车呼呼呼 发表于 2022-7-7 12:42
是的，current_s是计算区间的差值，用于和 s 比较判断是否满足条件。
px - px 是区间宽度，也就 ...
ok , 懂了 {:5_108:}
页:
[1]