Решение задачи Два массива и обмены с Codeforces

С пояснением   Просмотров: 203

Вам даны два массива a и b, оба состоят из n положительных (больших нуля) целых чисел. Также вам задано число k.

За один ход вы можете выбрать два индекса i и j (1≤i,j≤n) и поменять местами ai и bj (i.e. ai становится bj и наоборот). Заметьте, что i и j могут совпадать или отличаться (в частности, обмен a2 с b2 или обмен a3 с b9 оба считаются приемлемыми ходами).

Ваша задача — назвать максимальную возможную сумму, которую вы можете получить в массиве a, если вы сделаете не более k таких ходов (обменов).

Вам нужно ответить на t независимых наборов тестовых данных.

Код 

#include <bits/stdc++.h>

using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n, k;
		cin >> n >> k;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		vector<int> b(n);
		for (auto &it : b) cin >> it;
		sort(a.begin(), a.end());
		sort(b.rbegin(), b.rend());
		int ans = 0;
		for (int i = 0; i < n; ++i) {
			if (i < k) 
                ans += max(a[i], b[i]);
			else 
                ans += a[i];
		}
		cout << ans << endl;
	}
	
	return 0;
}

         

Администратор Photo Автор: Администратор


Пояснение к задаче

Во время каждого хода мы можем брать минимальный элемент в a, максимальный элемент в b и поменять их (если минимум в a меньше, чем максимум в b). Если мы повторим эту операцию k раз, то мы получим ответ. Это можно сделать за O(n * n * n), O(n * n), но авторское решение работает за O(nlogn).



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES [email protected] Карта сайта