首页 > 试题广场 >

买房

[编程题]买房

在一条街上有n幢房子，标号从1到n，两个在标号上相差为1的房子视为相邻，这些房子中有k幢房子已有住户。
现你准备搬入这条街，你能搬入一幢房子的条件是这幢房子没有人住在里面，与此同时由于你非常热爱与邻居进行交流，故而你需要你所入住的房子两边上都有住户。

现要你求最小的可能符合要求的房子数，以及最大的可能符合要求的房子数。

Note: 就样例来说，#代表已有住户，-代表空位，这种情况（###---)，没有满足条件的房子，为最小，故输出0
最大的情况为(#-#-#-)，此种情况有二个位置满足条件，为最大，故输出2

输入的一行为测试用例数t(1 <= t <= 200000)，

接下来t行，每行含两个整数n和k，(1 <= n <= 1,000,000,000，0 <= k <= n)

对于每个用例输出最小的可能数以及最大的可能数

示例1

输入

算法知识视频讲解

恒成立

发表于 2021-09-18 21:21:37

import java.io.*; import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); 展开全文

恒成立

发表于 2021-09-18 21:23:50

import java.io.*; import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); 展开全文

牛客题解官

发表于 2020-06-05 18:41:26

题解：难度：二星考察点：思维，数形结合题解：数形结合显然如果把个连续排在一起，则一个满足条件的都不存在，很显然最小值为，接下来难点变成了求最大值。最大值的排列情况如下图所示：红色表示住户，黄色表示空地。显然上图所示这种情况能够组成最大值，假设有个住户，则会占据个方格，所以当时，满足条展开全文

xuheding

发表于 2022-09-07 00:11:22

对于最小的可能数把所有的房子都往一边靠，那么最小的可能数一定是0 对于最大的可能数，（1）比如#-#-#-- 这种情况，k=3，那么满足条件的房子，夹在中间，因此k-1。 (2)比如k=0或者k=1的情况，那么满足条件的房子为0 （3）比如#-#-###这种情况下，是在展开全文

c小白进击之路

发表于 2021-04-16 08:18:34

能够用图形表示的，绝不用文字 #include<stdio.h> int main() { int t,n,k,max; scanf("%d",&t); for(in 展开全文

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师贪心网易 2019 拼多多集团-PDD 数学 Java工程师

上传者：小小

难度：

31条回答 32收藏 7201浏览

查看代码