Oros Ioana Diana at 13:50, 18 May 2024

2024-05-18T13:50:57Z

Oros Ioana Diana: Pagină nouă: == Cerința == Se dă un vector de N numere naturale nenule, indexat de la 1.
Se cere să se raspundă la Q interogări de tipul: pentru un interval [l, r] din vector, aflați costul total mimin, al egalizării tuturor elementelor din interval. Într-un interval [l, r], puteți crește sau micșora fiecare element cu costul x unde x este diferența dintre valoarea nouă și valoarea inițială. Costul total este suma acestor costuri. == Date de intrare == pe prima lini...

2024-01-08T20:58:09Z

Pagină nouă: == Cerința == Se dă un vector de N numere naturale nenule, indexat de la 1. Se cere să se raspundă la Q interogări de tipul: *pentru un interval [l, r] din vector, aflați costul total mimin, al egalizării tuturor elementelor din interval. Într-un interval [l, r], puteți crește sau micșora fiecare element cu costul x unde x este diferența dintre valoarea nouă și valoarea inițială. Costul total este suma acestor costuri. == Date de intrare == *pe prima lini...

New page

== Cerința ==
Se dă un vector de N numere naturale nenule, indexat de la 1.
 
Se cere să se raspundă la Q interogări de tipul:
*pentru un interval [l, r] din vector, aflați costul total mimin, al egalizării tuturor elementelor din interval.
Într-un interval [l, r], puteți crește sau micșora fiecare element cu costul x unde x este diferența dintre valoarea nouă și valoarea inițială. Costul total este suma acestor costuri.
== Date de intrare ==
*pe prima linie numărul N.
*pe a doua linie N numere naturale nenule : x1 ,x2 , … xN.
*pe a treia linie numărul Q.
*pe următoarele Q linii 2 numere: l, r.
== Date de ieșire ==
Se vor afișa Q numere pe fiecare linie, reprezentând constul total minim, al fiecărui interval l r.
== Restricții și precizări ==
*'''1 ≤ N, Q ≤ 100.000'''
*'''1 ≤ l ≤ r ≤ 100.000'''
*'''1 ≤ xi ≤ 1.000.000.000'''
== Exemplul 1 ==
; Intrare
: 9
: 3 2 16 15 12 6 20 4 5
: 3
: 2 7
: 2 2
: 3 8
; Ieșire
: 31
: 0
: 29
 
== Exemplul 2 ==
; Intare
: 5
: 1 2 3 4 5
: 2
: 1 4
: 3 5
; Ieșire
: 9
: 6
 
== Rezolvare ==
<syntaxhighlight lang="python" line>
#1901 - Median Heaps
def is_valid_input(N, Q, x_values, queries):
if not (1 <= N <= 100000 and 1 <= Q <= 100000):
return False
if not all(1 <= xi <= 1000000000 for xi in x_values):
return False
if not all(1 <= l <= r <= N for l, r in queries):
return False
return True

def minimize_costs(N, x_values, Q, queries):
result = []
for l, r in queries:
interval = x_values[l - 1:r]
min_value = min(interval)
cost = sum(min_value - xi for xi in interval)
result.append(cost)
return result

if __name__ == "__main__":
try:
# Citire date de intrare
N = int(input())
x_values = list(map(int, input().split()))
Q = int(input())
queries = [tuple(map(int, input().split())) for _ in range(Q)]

# Verificare restricții
if not is_valid_input(N, Q, x_values, queries):
print("Fals")
else:
# Calcul și afișare rezultate
results = minimize_costs(N, x_values, Q, queries)
for result in results:
print(result)

except ValueError:
print("Fals")

</syntaxhighlight>

== Explicatie ==
Pentru intervalul [2, 7], costul total minim este 31, deoarece egalizăm fiecare număr din interval cu 12.
 
Pentru intervalul [2, 2], costul total minim este 0, deoarece avem un singur element în interval.
 
Pentru intervalul [3, 8], costul total minim este 29, deoarece egalizăm fiecare număr din interval cu 12.

1901 - Median Heaps - Revision history

Oros Ioana Diana at 13:50, 18 May 2024