4

我在 Android 上开发应用程序时遇到了一个问题。然而，问题是：

有x盒子和y球的地方x <= y，我想把球按顺序放在盒子里。例如：3盒；box A,box B和box C- 和 5 个球; ball 1, ball 2, ball 3, ball 4, ball 5.

我需要的是把第一个球ball 1放在里面box A，ball 5里面box C和其他的球都分布在它们之间（如果一个盒子的球比其他的多，这无关紧要）。这是一个模拟问题的循环（缺少增量值）：

int boxCount = 0; // first box is 0 and last box is x
int numOfBalls = y;
for(int i = 0; i < numOfBalls; i++, boxCount += ???)
{
    boxes.get(boxCount).add(balls.get(i));
}

我应该使用什么方程来代替???解决问题？

编辑：

由于x <= y，这意味着：

  • 没有一个框应该是空的。
  • 盒子的球数之差不应大于1。

编辑2

，in order我的意思是：

A   B   C
---------
1   3   5
2   4

不是

A   B   C
---------
1   2   3
4   5
4

4 回答 4

3

您可以在第一个盒子(int)n/k中的每个盒子中分配球，k-1在最后一个盒子中分配其余的球。这将是最简单的编码。

有了这个：boxCount += (i % (numOfBalls/numOfBoxes) == 0 && boxCount < numOfBoxes-1 ? 1 : 0)

于 2012-04-09T20:12:08.487 回答
3 
int flag;
int lastBallAdded = 0;
int k = numOfBalls/numOfBoxes;
int m = numOfBalls%numOfBoxes;

for(int i = 0; i < numOfBoxes; i++, lastBallAdded+=k+flag) {
    flag = i<m;

    for(int j=lastBallAdded;j<lastBallAdded + k + flag;j++) 
        boxes.get(i).add(balls.get(j));
}

这是此解决方案背后的原因：

根据问题的定义，算法应该k= numOfBalls/numOfBoxes在每个盒子里放球，除了第一个m = numOfBalls%numOfBoxes盒子，你应该放k+1球。

您也可以将其写为

int i;
for(i = 0; i < m; i++) {
    //add k+1 balls
}

for(;i<numOfBoxes; i++) {
    //add k balls
}
于 2012-04-09T20:27:06.340 回答
2 
int ball = 0;
for( int box = 0; box < x; ++box )
   while ( x * (ball+1) <= y * (box+1) )
      boxes.get(box).add(balls.get(ball++));

循环不变：左边的k盒子包含k/x球的一部分（圆形）。

于 2012-04-09T20:49:18.233 回答
1

好的，新的尝试：

boxCount = ((i * nbrOfBoxes) / nbrOfBalls) + 1;

请注意，球的索引从 0 到 4 编号（如在 for 循环中）。删除+ 1if yo 希望 boxCount 从零开始。

于 2012-04-09T20:29:16.107 回答