[2021.11.14]UPC-计算机2021随堂测验第四场-21234 Problem G 买房子

本文主要是介绍[2021.11.14]UPC-计算机2021随堂测验第四场-21234 Problem G 买房子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

马克思姆想要在一座大房子里面买一套公寓套房，已知有n个套房排成一排，其中有k套房已经被人住了。马克思姆喜欢串门，所以他想要住旁边有人住的房子。我们规定一套房子如果是好房子，那么相邻的房子中至少有一个房子已经有了人住了。但是马克思姆只知道有k个房子有人住了，他并不知道具体哪k个房子住了人。帮助马克思姆算出最少有几个好房子，最多有几个好房子。

输入

两个整数n,k （1<=n<=109,0<=k<=n）

输出

输出两个整数，分别表示最少有几个好房子，最多有几个好房子。

样例输入 Copy

6 3

样例输出 Copy

1 3

题解

该题其实有一点贪心算法的感觉。

要分为两类讨论，

当 k<=n/3时，我们可以采取最优放法，让每个住人的房子旁边的房子都是空房子，好房子数为k*2。

当k>n/3时，最优放法放完之后，每再住一个人，好房子就要减少一个，所以好房子数为(n/3*2)-(k-n/3)化简可得 好房子数为n-k。

要注意 k为0的特殊情况

#include <cstdio>
int main() {int n,k;scanf("%d %d",&n,&k);if(!k||k==n){printf("0 0");return 0;}elseprintf("1 ");if(k<=n/3){printf("%d",k*2);}else{printf("%d",n-k);}return 0;
}

这篇关于[2021.11.14]UPC-计算机2021随堂测验第四场-21234 Problem G 买房子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---