Codeforces 854B Maxim Buys an Apartment：贪心

题目链接：http://codeforces.com/contest/854/problem/B

题意：

　　有n栋房子从1到n排成一排，有k栋房子已经被售出。

　　现在你要买一栋“好房子”。

　　一栋房子是“好房子”的要求：（1）没被售出（2）至少有一栋已售出的房子与他相邻（有邻居）

　　问你可能的好房子总数量的最小值和最大值。

题解：

　　贪心。

　　最小值：

　　　　从第1栋房子开始紧挨着往右共k栋全都售出了，好房子只有一栋就是第k栋楼的右边一栋。

　　　　特判：k == 0 || n == k：没有好房子，输出0。

　　最大值：

　　　　最完美情况为：每一栋已出售的房子紧挨的左右两边都没有出售，所以都是好房子。

　　　　如果左右两边的好房子 + 售出的房子 <= 总房子数，即k*2<=n-k：那么存在完美情况，答案为k*2（左右两边各一栋）。

　　　　否则除了售出的k栋房子之外，剩下的都是好房子。答案为n-k。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 using namespace std;

 int n,k;

 int maxn,minn;

 int main()

 {

     cin>>n>>k;

     if(k*<=n-k) maxn=k*;

     else maxn=n-k;

     if(n==k || k==) minn=;

     else minn=;

     cout<<minn<<" "<<maxn<<endl;

 }

巴特西

Codeforces 854B Maxim Buys an Apartment：贪心

最新文章

热门文章