首页 > 试题广场 > 买房
[编程题]买房
  • 热度指数:3703 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
在一条街上有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

输入

6
1 0
1 1
2 0
2 1
2 2
6 4

输出

0 0
0 0
0 0
0 0
0 0
0 2
"""
规律题,最小值都为0,最大值为 min(n - k, k - 1)
"""

if __name__ == "__main__":
    t = int(input().strip())
    for _ in range(t):
        n, k = map(int, input().strip().split())
        if n < 3 or k >= n or k < 2:
            ans = 0
        else:
            ans = min(n - k, k - 1)
        print(0, ans)

发表于 2019-07-18 19:38:34 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int t,n,k;
    cin>>t;
    while(t--){
        cin>>n>>k;
        int s = n-k;
        cout<<0<<" ";
        if(n<3 || k<=1)
            cout<<0<<endl;
        else
            cout<<min(k-1, s)<<endl;
    }
    return 0;
}

发表于 2019-08-26 01:25:48 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long n,k;
        cin>>n>>k;
        if(k>n-k)
        {
            if(n-k>=0)
                cout<<0<<" "<<n-k<<endl;
            else
                cout<<0<<" "<<0<<endl;
        }
        else 
        {
            if(k-1>=0)
                cout<<0<<" "<<k-1<<endl;
            else
                cout<<0<<" "<<0<<endl;
        }
    }
    return 0;
}

编辑于 2019-07-11 20:52:58 回复(0)
可以让已经入住的邻居全部紧密排列在一起,所以最少的情况一定是0。而最多的就是题干中举出的相间情况,为k户已入住人家的内间隔数,即k-1,但k-1又不能比剩下的位置n-k大,所以最大只能是n-k和k-1中小的那个。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        while(t-- > 0){
            String[] temp = br.readLine().trim().split(" ");
            long n = Long.parseLong(temp[0]), k = Long.parseLong(temp[1]);
            // 最小肯定是0
            long min = 0;
            // 最大不会超过k-1,但是又不能比剩余能入住的房子n-k多
            long max = 0;
            max = Math.min(n - k, Math.max(k - 1, 0));
            System.out.println(min + " " + max);
        }
    }
}


编辑于 2021-01-30 18:36:57 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int a,b,mid;
        cin>>a>>b;
        mid=a/2;
        if(b<=1)
            cout<<0<<" "<<0<<endl;
        else{
            if(a&1)
                mid++;
            cout<<0<<" "<<(b<=mid ? b-1:a-b)<<endl;
        }
    }
    return 0;
}

发表于 2019-10-14 20:05:19 回复(0)

我的

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int a=sc.nextInt();
        long min=0,max;
        for(int i=1;i<=a;i++){
            long n=sc.nextLong();
            long k=sc.nextLong();
            if(n<3||k<2){
                max=0;
            }else{
                if(n%2==0){//n为双数
                    if(k==n/2||k==n/2+1){
                        max=n/2-1;
                    }else if(k<n/2){
                        max=k-1;
                    }else{
                        max=n-k;
                    }
                }else{//n为单数
                    if(k==n/2+1){
                        max=n/2;
                    }else if(k<n/2+1){
                        max=k-1;
                    }else{
                        max=n-k;
                    }
                }
            }
            System.out.println(min+" "+max);
        }
    }
}

别人的浓缩版

import java.util.*;
public class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int test = sc.nextInt();
    for(int i=0; i<test; i++){
     int n = sc.nextInt();
     int k = sc.nextInt();
      //住满了
      if(n == k || n<3 || k<2){
        System.out.println("0 0");
      }
      else{
        int result = (n/2 >= k)?(k-1):(n-k);
        System.out.println("0 "+result);
      }
    }
  }
}
发表于 2019-09-20 00:40:10 回复(0)

Java

注意k有可能为0。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            if (n < 3) {
                System.out.println(0 + " " + 0);
            } else {
                if (n - k < k) {
                    System.out.println(0 + " " + (n - k));
                } else {
                    System.out.println(0 + " " + (k - 1 > 0 ? k - 1 : 0));
                }
            }
        }
    }
}
发表于 2019-07-06 11:02:21 回复(0)
#include<iostream>
int main()
{
    long t;
    long long n,k;
    while(std::cin>>t)
    {
        long long a=0;
        for(long i=0;i<t;i++)
        {
            std::cin>>n>>k;
            if(k<2)a=0;
            else
            {
                if(n%2==0)
                {
                    if(k<=n/2)a=k-1;
                    else if(k==n/2+1)a=k-2;
                    else a=n-k;
                }
                if(n%2==1)
                {
                    if(k<=(n+1)/2)a=k-1;
                    else a=n-k;
                }
            }
            std::cout<<0<<" "<<a<<std::endl;
        }
    }
    return 0;
}
发表于 2020-09-15 17:19:02 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-->0){
            int n = sc.nextInt();
            int k = sc.nextInt();
            if(k<2||k==n||n<3){
                System.out.println(0+" "+0);
            }else if(n-k<k){
                System.out.println(0+" "+(n-k));
            }else{
                System.out.println(0+" "+(k-1));
            }
        }
    }
}

为啥复杂度这么高
编辑于 2020-08-31 19:14:44 回复(0)
t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    print(0, max(min(k - 1, n - k), 0))

发表于 2020-08-06 13:50:11 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        if(n<3||k==0||k>n){cout<<0<<" "<<0<<endl;}
        if(n>=3&&k>0){cout<<0<<" "<<min(n-k,k-1)<<endl;}
    }
    return 0;
}

发表于 2020-07-31 10:26:20 回复(0)
t = int(input())
for i in range(t):
    n, k = list(map(int, input().split(' ')))
    if k <= 1&nbs***bsp;n-k <= 1:
        print('{} {}'.format(0,0)) 
    elif (n-n//2) < k:
        print('{} {}'.format(0,n-k))
    elif (n-n//2) >= k:
        print('{} {}'.format(0,k-1))

发表于 2020-07-30 16:17:10 回复(0)
我没别人那么聪明,所以分的情况多一些。
#include <iostream>
#include <vector>

using namespace std;

int main(){
    int numCyc;
    cin >> numCyc;
    while(numCyc--){
        //最差怎么都是0
        cout << 0 << ' ';
        int n, k;
        cin >> n >> k;
        //无论是总户数还是已住户数,只要小于2,就不行
        if (n <= 2 || k <= 2)
            cout << 0 << endl;
        //如果已住小于总数的一半
        else if (k <= (n+1) / 2)
            cout << k-1 << endl;
        //如果已住大于总数的一半
        else{
            //总户数为奇数的情况
            if (n % 2 == 0)
                cout << n-k << endl;
            //总户数为偶数的情况
            else
                cout << n/2 + (n+1)/2 - k << endl;
        }
    }
    return 0;
}


发表于 2020-07-15 20:38:08 回复(0)
#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        cout<<0<<" ";
        if(n<3||k<2){
            cout<<0<<endl;
            continue;
        }

        int m = n-k;
        --k;
        cout<<min(m,k)<<endl;

    }
    return 0;
}
发表于 2020-06-09 00:12:45 回复(0)
t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    if n <= 2&nbs***bsp;n - k == 0&nbs***bsp;k == 1:
        print('0 0')
    else:
        s = '0 '
        a = min(n-k, k-1)
        s = s + str(a)
        print(s)

发表于 2020-05-03 10:11:27 回复(0)
#include<iostream>
(720)#include<cstring>
#include<cmath>
using namespace std;
int main()
{
    int t;
    cin>>t;
    int A[t][3];
    memset(A,0,sizeof(A));
    for(int i=0;i<t;i++)
    {
        cin>>A[i][0]>>A[i][1];
        int cmp = A[i][1];
        if(cmp-1 < 0)
        {
            A[i][2] = 0;
        }else
        {
            int cmp1 = A[i][0] - A[i][1];
            A[i][2] = min(cmp1,cmp-1);//在空位和夹空中,取最小值
        }
        
    }
    for(int i=0;i<t;i++)
    {
        cout<<0<< " " <<A[i][2]<<endl;
    }
    return 0;
}
新手,
发表于 2020-04-21 16:34:33 回复(0)
开始没有考虑k>n的情况,通过率就一直70%,找了好久才发现
var n = readline();
for(var i =0 ;i<n;i++){
    var arr = readline().split(" ").map(Number)
    if(arr[0]<=2){
        console.log('0 0');
    }else{
        var max = arr[0]/arr[1]>=2?arr[1]-1:(arr[0]-arr[1]);
        console.log("0 "+Math.max(max,0))
    }
}

发表于 2020-04-07 10:41:54 回复(0)
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            long n = sc.nextInt();
            long k = sc.nextInt();
            if (n <= 2 || k <= 1 || n == k) {
                System.out.println(0 + " " + 0);
                continue;
            } else {
                long gap = k - 1;
                long selections = n - k;
                long max = Math.min(gap, selections);
                System.out.println(0 + " " + max);
            }
        }
    }
}

发表于 2020-04-04 20:24:25 回复(0)
过80% 超时的Java老哥有吗
import java.util.Scanner;
public class Main15 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int t = 0; t < T; t++) {
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            System.out.print( 0 + " ");
            if(n >= 2*k){
                System.out.println(Math.max(k - 1, 0));
            }
            else System.out.println(n-k);
        }
    }

发表于 2019-12-12 15:59:04 回复(0)
usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingSystem.Text;
usingSystem.Threading.Tasks;
 
namespace买房
{
   
    classProgram
    {
        staticvoidMain(string[] args)
        {
            //输入
            intcaseNum =int.Parse(Console.ReadLine());
            Street[] streets =newStreet[caseNum];
            for(inti = 0; i < caseNum; i++)
            {
                strings = Console.ReadLine();
                string[] sArray = s.Split(' ');
                streets[i] =newStreet(int.Parse(sArray[0]),int.Parse(sArray[1]));
            }
 
            //输出
            foreach(var streetinstreets)
            {
                Console.WriteLine($"{street.min} {street.max}");
            }
 
            Console.Read();
        }
 
 
    }
    //抽象一下
    classStreet
    {
        publicintn;
        publicintk;
        publicStreet(intn,intk)
        {
            this.n = n;
            this.k = k;
        }
        publicintmin = 0;
        publicintmax
        {
            get=> (n - k > k - 1 ? k - 1 : n - k)>0? (n - k > k - 1 ? k - 1 : n - k):0;
        }
    }
}
发表于 2019-10-09 17:24:48 回复(0)