Мінімальна сума конструкції#12262

Мінімальна сума конструкції (Розбір)

Автор проблеми:	Hasan Saleh (MathModel)
Підготовлено:	Hasan Saleh (MathModel)
Редаговано:	Hasan Saleh (MathModel)

Розв'язок

Вам потрібно побудувати масив $A$ довжини $n$ так, щоб $1 \leq A_{i} \leq n$ 1 \le A_i \le n, $\sum_{i = 1}^{n} A_{i} = a$ \sum_{i=1}^n A_i = a і $\sum_{i = 1}^{n} min (A_{i}, b) = c$ \sum_{i=1}^n \min(A_i,b) = c. Умова з мінімумом є обмежувальною, тому спочатку ми зробимо цю суму правильною, а потім виправимо реальну суму.

Зверніть увагу, що нам ніколи не потрібно починати з значення, більшого за $min (b, n)$ , оскільки значення все одно обмежені $n$ , і будь-яке значення $> b$ дає той же внесок $b$ до обмеженої суми. Нехай $B = min (b, n)$ B = \min(b,n). Якщо ми встановимо

A_{i} = B для всіх i = 1, \dots, n,

A_i = B \quad \text{для всіх } i=1,\dots,n,

то ми наразі маємо

i = 1 \sum n min (A_{i}, b) = i = 1 \sum n B = n \cdot B,

\sum_{i=1}^n \min(A_i,b) = \sum_{i=1}^n B = n \cdot B,

і також

i = 1 \sum n A_{i} = n \cdot B .

\sum_{i=1}^n A_i = n \cdot B.

Назвемо цю поточну обмежену суму $tot = n \cdot B$ \text{tot} = n \cdot B.

Ми хочемо, щоб обмежена сума стала точною $c$ . Оскільки наразі кожне $A_{i} \leq B \leq b$ A_i \le B \le b, зменшення $A_{i}$ A_i на $1$ також зменшить $min (A_{i}, b)$ \min(A_i,b) на $1$ . Тому ми проходимо від $i = 1$ i=1 до $n$ і поки $tot > c$ \text{tot} > c намагаємось зменшити $A_{i}$ A_i. Для фіксованої позиції $i$ ми не можемо зменшити більше, ніж те, що ще є зайвим, і не можемо опуститися нижче $1$ , тому беремо

v = min {tot - c, A_{i} - 1, B - 1}

v = \min\{\, \text{tot} - c,\; A_i - 1,\; B - 1 \,\}

і виконуємо

A_{i} \leftarrow A_{i} - v, tot \leftarrow tot - v .

A_i \gets A_i - v,\quad \text{tot} \gets \text{tot} - v.

Після одного проходу рівність

i = 1 \sum n min (A_{i}, b) = c

\sum_{i=1}^n \min(A_i,b) = c

виконується, оскільки кожна одиниця, яку ми відняли від деякого $A_{i} \leq b$ A_i \le b, зменшила обмежену суму точно на $1$ .

Тепер ми перевіряємо реальну суму $\sum A_{i}$ \sum A_i. Якщо $b \geq n$ b \ge n, тоді $B = n$ B = n і $min (A_{i}, b) = A_{i}$ \min(A_i,b) = A_i для всіх $i$ , тому як тільки обмежена сума дорівнює $c$ , ми вже маємо $\sum A_{i} = c$ \sum A_i = c, і оскільки умова гарантує, що розв'язок існує, ми повинні мати $a = c$ a=c і ми закінчили.

Якщо $b \leq n$ b \le n, тоді після зменшення ми маємо правильну обмежену суму, але можливо

i = 1 \sum n A_{i} < a .

\sum_{i=1}^n A_i < a.

Щоб збільшити реальну суму, не змінюючи обмежену суму, ми торкаємось лише позицій з $A_{i} = b$ A_i = b. Якщо ми збільшуємо таке $A_{i}$ A_i до $b + δ$ b + \delta з $δ \leq n - b$ \delta \le n-b, тоді

min (A_{i}, b) = b (незмінно),

\min(A_i,b) = b \quad \text{(незмінно)},

але реальна сума збільшується на $δ$ . Тому ми знову скануємо і щоразу, коли $A_{i} = b$ A_i = b і поточна сума все ще $< a$ , ми додаємо

δ = min (a - sum, n - b)

\delta = \min(a - \text{sum},\; n - b)

до $A_{i}$ A_i. Оскільки проблема обіцяє, що розв'язок існує, ми знайдемо достатньо таких позицій, щоб досягти точної суми $a$ . Ми ніколи не порушуємо $A_{i} \leq n$ A_i \le n, оскільки ми лише підвищуємо з $b$ до максимуму $n$ .

Отже, конструкція є такою:

встановіть все на $B = min (b, n)$ B = \min(b,n);
зменшуйте з початку, щоб зробити обмежену суму рівною $c$ ;
якщо $b \leq n$ b \le n, підвищуйте лише позиції, які наразі дорівнюють $b$ , щоб зробити реальну суму рівною $a$ .

Складність становить $O (\sum n)$ \mathcal{O}(\sum n).

for _ in range(int(input())):
    n,a,b,c=map(int,input().split())
    base=min(b,n)
    res=[base]*n
    tot=n*base
    i=0
    while i<n and tot>c:
        v=min(tot-c,res[i]-1,base-1)
        if v>0:
            res[i]-=v
            tot-=v
        i+=1
    if b<=n:
        i=0
        while i<n and tot<a:
            if res[i]==b:
                v=min(a-tot,n-b)
                if v>0:
                    res[i]+=v
                    tot+=v
            i+=1
    print(*res)

Python