Qurban (Həll təhlili)

İpuçları:

1) Hər hansı bir mübadilə sayı massivini istənilən massivə çevirmək üçün ekvivalentdir.

2) $m$ dəyəri faktiki dəyərlə bağlı deyil.

3) Optimal yol, massivi azalan sıraya görə sıralamaq və bu əsasında tam ədədləri seçməkdir.

4) Problemin təsdiqi - tam massiv dövrlərini və qalan ən böyük elementləri yoxlamaq.

Həll

Biz sonsuz sayda mübadilə edə bilərik, bu da (sıralamanı dəyişmək) deməkdir, optimal seçim, massivi azalan sıraya görə sıralamaqdır və dövr xüsusiyyətlərini tətbiq edərək, $k$-nı k \bmod n olaraq $m$-dən m+k-1-ə qədər olan mövqelərdə, ən böyük ədədi öz mövqeyinə əlavə edirik, yəni, [ən böyük, daha kiçik, daha da kiçik, ..., ən kiçik], nəhayət, qalanı istənilən mövqeyə əlavə edirik, çünki bu seçilmiş sahəyə təsir etməyəcək.

Komplekslik O(n \log n) xəritələrdən istifadə səbəbindən.

for _ in range(int(input())):
    n, m, k = map(int, input().split())
    arr = list(map(int, input().split()))
    a = sorted(arr, reverse=True)
    r = k % n
    c = [None] * n
    for i in range(r):
        pos = (m - 1 + i) % n
        c[pos] = a[i]
    mp = {}
    for x in arr:
        mp[x] = mp.get(x, 0) + 1
    for i in range(r):
        mp[a[i]] -= 1
        if mp[a[i]] == 0:
            del mp[a[i]]
    rem = []
    for x, cnt in mp.items():
        rem.extend([x] * cnt)
    it = iter(rem)
    for i in range(n):
        if c[i] is None:
            c[i] = next(it)
    print(*c)