Maxim Buys an Apartment CodeForces

题意：已知一条街上有n幢房子，依次的编号为1~n，其中有k幢已经卖出去了但是不知道是哪k幢。当且仅当一幢房子没有卖出去且其两旁至少有一幢房子卖出去了的时候，认为这幢房子是好的。问这n幢房子中好的房子最多、最少可能有多少。

思路：简单的贪心（但是不小心可能错）。首先如果k==n或者k==0，那么显然不可能有任何好的房子。否则，当将所有的卖出去的房子的位置连续地放在街的一端时，好的房子的数量取到最小值1。当n>=k*3时，将n个房子按每三个为一段分开，其中任选k段使中间的那一个房子为卖出去的，那么这k段中每一段就有了一幢卖出去的房子和两幢好的房子，可以使好的房子的数量取到最大值k*2。如果n<k*3，先用n/3幢房子按n>=k*3的方法搞到2*[n/3]幢，剩下n-[n/3]*3套既不是卖出的又不是好的，然后如果n-[n/3]*3为1或2则在这剩下的几套中选出1套，显然分别能使好的房子数量分别增加0、1套，也就是如果n-[n/3]*3=0那么有2*[n/3]好的和k=[n/3]套已卖出的，如果n-[n/3]*3=1那么有2*[n/3]好的和k=[n/3]+1套已卖出的，如果n-[n/3]*3=2那么有2*[n/3]+1好的和k=[n/3]+1套已卖出的，三种情况都满足好的数量等于n-k。

易错点：3*k可能爆int，需要long long

 #include<cstdio>

 typedef long long LL;

 LL n,k;

 int main()

 {

     scanf("%lld%lld",&n,&k);

     if(n==k||k==)

     {

         printf("0 0");

         return ;

     }

     printf("1 ");

     if(n>=k*)

         printf("%lld",k*);

     else

         printf("%lld",n-k);

     return ;

 }

巴特西

Maxim Buys an Apartment CodeForces - 854B

最新文章

热门文章