【二分】LOJ 1088 Points in Segments
KIDx 的解题报告题目链接：http://lightoj.com/volume_showproblem.php?problem=1088
题意：给一串单调递增的数，输入x, y，问>=x且<=y的数有多少个？
二分要点：设初始下界为l，上界为r 二分进行条件：while (l < r)
①要找单调区间中尽量小的符合条件的量，则mid的可达范围应该是右开区间
若符合，令r = mid；否则令l = mid + 1推进，因此mid = (l+r) / 2，这是导致区间右开的根本原因
r 即为二分结果
②要找单调区间中尽量大的符合条件的量，则mid的可达范围应该是左开区间(l, r]；
若符合，令l = mid；否则令r = mid - 1不可推进，因此需要mid = (l+r+1) / 2推进，这是导致区间左开的根本原因
l即为二分结果
#include <iostream>using namespace std;#define M 100005 int num; int main(){ int t, cc = 1, l, r, mid, i, a, b, x, y, n, k; bool flag; scanf ("%d", &t); while (t--) { scanf ("%d%d", &n, &k); for (i = 0; i < n; i++) scanf ("%d", num+i); printf ("Case %d:\n", cc++); while (k--) { flag = false; scanf ("%d%d", &x, &y); l = 0, r = n;//可达范围：左闭右开区间 while (l < r) { mid = (l+r) / 2; if (num >= x) { r = mid; flag = true; } else l = mid + 1; } if (!flag)//没有一个数满足>=x { puts ("0"); continue; } flag = false; a = r; l = -1, r = n - 1;//可达范围：左开右闭区间 while (l < r) { mid = (l+r+1) / 2; if (num <= y) { l = mid; flag = true; } else r = mid - 1; } if (!flag)//没有一个数满足<=y { puts ("0"); continue; } b = l; printf ("%d\n", b-a+1);//输出x，y之间有多少个数 } } return 0;}
页:
[1]