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;
}
上一篇:PHP魔术方法在框架中的应用


下一篇:caffe中python接口的使用