算法：將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（四捨五入）。