Самый простой способ разбить n объектов на m множеств, где m не делит n?

Question

Самый простой способ разбить n объектов на m множеств, где m не делит n?

У меня есть два целых числа m а также n, с m < n, В общем, m не делит n,

Скажи это n = m*q + r, где q целое число n а также m, а также r это остаток (0 <= r < m). Если мы разделим n объекты в m коробки как можно более однородно, r из коробок будет содержать q+1 объекты и остальные коробки будут содержать q объекты. Предположим, что объекты индексируются из 1 в nи что они вставляются в ящики по порядку. Кроме того, предположим, что первый r коробки содержат q+1 объекты.

Я хочу написать функцию, которая возвращает список индексов i1, i2, ..., imтакой, что i1 индекс наименьшего объекта в первом поле, i2 индекс наименьшего объекта во втором блоке и т. д.

Я могу придумать пару способов написать эту функцию самостоятельно, но я думаю, что они слишком сложны. Я считаю, что есть простой способ сделать это, которого я не вижу.

0

algorithm c++integer-arithmetic

Решение

Другие решения

добавлять q возражает против каждой коробки. Если поле является одним из n - m*q == n % m Сначала добавьте еще один объект:

std::vector<int> starts_of(int n, int m)
{
std::vector<int> v;

int q = n / m;
int s = 1;

for (int i = 0; i < m; i++) {
v.push_back(s);
s += q;
if (i < n % m) s++;
}

return v;
}

1

r = n % m
d = n / m
//with two loops without conditionals:
for i = 0..r - 1
I[i] = 1 + i * d  + i
for i = r..m - 1
I[i] = 1 + i * d + r
//or with single loop:
for i = 0..m - 1
I[i] = 1 + i * d  + min(i, r)

0

Источник

Accepted Answer

Хорошо, я не совсем понял, что вы хотите сказать, «вставив в коробки по порядку», поэтому я предложу вам решение для 2 возможных значений.

а) Объекты вставляются в поля следующим образом:

9|
5|6|7|8
1|2|3|4

в этом случае решение довольно простое: просто выведите все числа от 1 до m.

Код:

function foo(int n, int m) {
for (int k=1; k<=m; k++)
cout<<k<<endl;
}

б) Объекты вставляются в коробки следующим образом:

3|6|
2|5|8|10
1|4|7|9

в этом случае для каждого блока объект с наименьшим индексом в блоке k равен: (n / m) * (k — 1) + min (k, n% m + 1)

Код:

function foo(int n, int m) {
for (int k=1; k<=m; k++)
cout<<(n / m) * (k - 1) + min(k, n % m + 1)<<endl;
}

2