算法：将y球放入x盒子中，其中x <= y

Question

我在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

---

EDIT2

通过in order盒子球数之间的差异，我的意思是这样的：

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

不

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

Answer 1

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 
} 

Answer 2

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

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

Answer 3

好了，新的尝试：

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

注意，球的索引编号为0至4（如for循环） 。如果您希望boxCount为零，请删除+ 1。

Answer 4

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（四舍五入）。