【2分】LOJ 1088 Points in Segments

【二分】LOJ 1088 Points in Segments

KIDx 的解题报告

?

题目链接：http://lightoj.com/volume_showproblem.php?problem=1088

?

题意：给一串单调递增的数，输入x, y，问>=x且<=y的数有多少个？

?

二分要点：设初始下界为l，上界为r? 二分进行条件：while (l < r)

①要找单调区间中尽量小的符合条件的量，则mid的可达范围应该是右开区间[l, r)；

若符合，令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[M]; 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[mid] >= 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[mid] <= 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;}

?