تضحية (شرح الحلول)

نصائح:

1) لاحظ أن أي عدد من التبادلات يعادل ترتيب المصفوفة إلى أي مصفوفة.

2) قيمة $m$ لا تهم في القيمة الفعلية.

3) الطريقة المثلى هي فرز المصفوفة بترتيب تنازلي واختيار الأعداد بناءً على ذلك.

4) التحقق من المشكلة - التحقق من دورات المصفوفة الكاملة وأكبر العناصر المتبقية.

الحل

يمكننا إجراء عدد لا نهائي من التبادلات، مما يعني أيضًا (تغيير الترتيب)، الخيار الأمثل هو فرز المصفوفة بترتيب تنازلي، ونطبق خصائص الدورات، مع تعيين $k$ إلى k \bmod n من المواقع $m$ إلى m+k-1، نضيف أكبر عدد إلى موقعه، أي، [الأكبر، الأصغر، الأصغر حتى، ...، الأصغر]، وأخيرًا، نضيف الباقي إلى أي موقع لأنه لن يؤثر على المنطقة المختارة.

التعقيد O(n \log 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)