ios笔试题算法_iOS笔试：一道京东编程题的解决方法

前两天在考京东的笔试题时，一道大题编程题未做出来，然后就接了图打算考试结束再思考。在今天终于有了一个比较清晰的思路，决定在博客中记录一下。

题目如下：

题目

笔试题.png

想法

想要使得>=K的堆数最多，那么先不想着“相邻堆石头数不能相等”这个条件，最多的堆数肯定就是N/K了。

举例说，N=6,K=2，那么输出就为3了。

但是，现在有了“相邻堆石头数不能相等”这个条件，那么在(6，2)的输入中，就不能有2，2，2这样的排列了。那就在相邻的堆中间插入1就能使得满足条件的堆数目最多。

那么现在我就把k个石头放一堆，1个石头再放一堆，然后把它们看做一组，那么大致可以把这样的组数看做是最后的答案了。

如下图：

(7 2).jpg

这是(7 2)情况，把2颗一堆，1颗一堆，再把两堆当做一组，这样就有2组，剩余还有1颗。那么排列顺序为：1，2，1，2，1。输出为2。

在如下图：

(8 2).jpg

这是(8 2)情况，也是有两组，但是还有剩余两颗，那么最后那两颗也是满足条件的一堆。所以排列顺序为2，1，2，1，2。

综上，可以得出一个公式了：设组数为a，剩余个数为b，那么有：

N/(K+1) = a+b

但是a并不是最后的输出，还需要比较b与k是否相等：

if (b == K)

a = a+1;

其实b与K是否相等就决定了1和k哪个堆放在前面。

但是！这样还没有结束，因为还有一个特殊情况，那就是k=1的时候，这时候再用k+1是不满足“相邻堆石头数不能相等”这个条件的。那么就只能用k+2代替了。k=1的时候不需要想得太麻烦，很简单嘛，1 2 1 2这样一直下去好了，到时候有几堆就输出几。

代码

#include

int main(){

int n, k, a, b;

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

if (k != 1) {

a = n/(k+1);

b = n%(k+1);

if (b == k) {

printf("%d", a+1);

} else {

printf("%d", a);

}

} else {

a = n/(k+2);

b = n%(k+2);

if (b == 0) {

printf("%d", a*2);

} else {

printf("%d", a*2+1);

}

}

return 0;

}

最后

因为笔试已经结束了，没有条件再去核对代码是否AC，只能通过手动输入来判断是否正确。

在笔试的时候，有限时间内要有思路并敲出代码还是有很大的难度的，事情说到底还是自己太菜。现在满脑子都是京东不要我了京东不要我了京东不要我了。委屈极了。

更新

感谢 旅徒冰迹 的指出，上面代码存在一个问题。

当输入为(7,2)的时候，我的代码会排序成1 2 1 2 1，而正确的答案为2 3 2，其实是把最左边的1和最右边的1都加到中间的那个1去了。

那么现在得确定什么时候会出现这样的问题。我发现：当k=2且刚好排序后左右两侧都为1的情况下，会出现这样的问题。

设想，当k>=3时，就算把两侧的1都加过来，还是不能满足条件；当两侧不都为1时，也不能满足条件。

所以代码更新如下：

#include

int main(){

int n, k, a, b;

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

if (k == 1) {

a = n/(k+2);

b = n%(k+2);

if (b == 0) {

printf("%d", a*2);

} else {

printf("%d", a*2+1);

}

} else if (k == 2) {

a = n/(k+1);

b = n%(k+1);

if (b == 0) {

printf("%d", a);

} else {

printf("%d", a+1);

}

} else {

a = n/(k+1);

b = n%(k+1);

if (b == k) {

printf("%d", a+1);

} else {

printf("%d", a);

}

}

return 0;

}