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;
}
分享到:
相关推荐
使用php做的,google的API客户端的连接程序的例子代码,主要是调用google的API的连接程序,简单全面供给各类学习参考
Loj X 使创建真正的计算单元甚至小型完整处理器成为可能。 除了逻辑门,存储盒和程序阅读器可以集成到电路中。
log4j配置文档,jar包
log4j配置
scicloj.github.com:Scicloj网站
的做题记录 Updates: ...2021.04.03 Luogu4719 Luogu4980 LOJ6538 2021.04.02 Luogu5298 Luogu6619 2021.04.01 Luogu5212 2021.03.21 Luogu4384 2021.03.30 Luogu3804 Luogu6139 2021.03.29 Luogu7470 2021
帕拉iniciarØprojeto EM阵营FOI utilizadoØCOMANDO yarn create react-app moveit --template=typescript ,ONDE moveit éØ诺姆做projetoË --template=typescript éØCOMANDO对inciar-LOJáCOM打字稿。
OICodeRepository zhylj 2019.10.1从今起,我就把代码存在这里,欢迎大家帮我D (c) e (o) b (p) u (y) g代码存放优先级:xxOI =罗古> Poj = loj> Bzoj不太可能会存放在多个地方。请查找同内容题。不保证一定...
包含 mybatis-3.3.0;log4j-1.2.17;junit-4.12;javassist-3.4.GA;hamcrest-all-1.3