最新消息:380元/半年,推荐全网最具性价比的一站式编程学习平台码丁实验室

信息学奥赛题库- 分组

C++ 少儿编程 1283浏览 0评论

友情提示:380元/半年,儿童学编程,就上码丁实验室

【题目描述】

社区有$n$个居民,每个居民有一定的地位和年龄,$r_i$表示第$i$个人的地位,$a_i$表示第$i$个人的年龄。

最近社区里要举行活动,要求几个人分成一个小组,小组中必须要有一个队长,要成为队长要满足以下条件:

①、队长在小组中的地位应该是最高的(可以并列第一);

②、小组中其他成员的年龄和队长的年龄差距不能超过$K$。

有些人想和自己亲密的人组在同一个小组,同时希望所在的小组人越多越好。比如$x$和$y$想在同一个小组,同时希望他们所在的小组人越多越好,当然,它们也必须选一个符合上述条件的队长,那么问你,要同时包含$x$和$y$的小组,最多可以组多少人?

【输入】

第一行两个整数$n$和$K$。

接下来一行输入$n$个整数:$r_1, r_2, …, r_n$。

接下来一行输入$n$个整数:$a_1, a_2, …, a_n$。

接下来输入$Q$表示有$Q$个询问。

接下来$Q$行每行输入$x, y$,表示询问:当$x$和$y$组在同一个小组,它们小组最多可以有多少人($x$和$y$也有可能被选为队长,只要它们符合条件)。

【输出】

对于每个询问,输出相应的答案,每个答案占一行。

当$x$和$y$无法在同一组时,输出$-1$(比如$x$的年龄是$1$, $y$的年龄是$100$,$K=1$,无论谁当队长,$x$和$y$两者中,总会有人跟队长的年龄差距超过$K$,那么输出$-1$)。

【输入样例】

5 1
1 5 4 1 2
4 4 3 2 2
4
5 3
2 3
2 5
4 1

【输出样例】

4
3
-1
4

【提示】

【样例解释】

询问1:当第$5$个人和第$3$个人想在一组时,小组成员可以有${1,3,4,5}$,选择$3$当队长,而$2$不可以加入,因为$2$加入的话,$5$和$2$的年龄差距为$2$,超过$K=1$了。

询问2:当第$2$个人和第$3$个人想在一组时,可以选择${1,2,3}$。

询问3:当$2$和$5$想在一起时,无法满足要求。

询问4:当$4$和$1$想在一起时,可以选择${1,3,4,5}$。

【数据规模】

对于20%的数据:$2≤n≤100,0≤k≤100,1≤r_i, a_i≤100,1≤q≤100$。

对于40%的数据:$2≤n≤1000,0≤k≤1000,1≤r_i, a_i≤1000,1≤q≤1000$。

对于60%的数据:$2≤n≤10^4,0≤k≤10^9,1≤r_i, a_i≤10^9,  1≤q≤10^4$。

对于100%的数据:$2≤n≤10^5,0≤k≤10^9,1≤r_i, a_i≤10^9,1≤q≤10^5,1≤x, y≤n, x≠y$。

您必须 登录 才能发表评论!