Language: C++

#include <algorithm>
#include <climits>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;

#define loop(i, times) for(int i = 0; i < times; i++)
#define seloop(i, start_index, end_index) for(int i = start_index; i < end_index; i++)
#define eqseloop(i, start_index, end_index) for(int i = start_index; i <= end_index; i++)

#include <iostream>
#include <map>
#include <vector>

using namespace std;

class NyaGadgetVector
{
public:
	/**
	@brief 加算関数
	@note
	 collectionの全要素にadd_valueだけ値を加算する
	**/
	template<typename T> static void Add(vector<T>& collection, T add_value)
	{
		for (auto& e : collection)
			e += add_value;
	}
	/**
	@brief 全要素変更関数
	@note
	 collectionの全要素をchange_valueに変更する
	**/
	template<typename T> static void ChangeAll(vector<T>& collection, T change_value)
	{
		for (auto& e : collection)
			e = change_value;
	}
	/**
	@brief 同じ要素の個数を数える関数
	@note
	 コンテナinput_collectionの同じ要素の個数を数えてoutput_collectionに結果を格納する。
	 output_collectionの第一引数には要素の値、第二引数には要素の個数が格納される。
	-------------------------------------------------------------------------------------
	[sample code]
	int main() {
		vector<long> input_collection = {10000000000, 10000000000, 2, 1, 2, 2, 2};
		vector<pair<long, int>> count_collection;			// p.first=value, p.second=size
		NyaGadgetVector::CountValue<long>(input_collection, count_collection);

		for (const auto& e : count_collection)
			cout << "(" << e.first << "," << e.second << ")";
		return 0;
	}
	[output]
	(1,1)(2,4)(10000000000,2)
	**/
	template<typename T> static void CountValue(const vector<T>& input_collection, vector<pair<T, int>>& output_collection)
	{
		map<T, int> count_collection;
		for (const auto& e : input_collection)
			count_collection[e] += 1;

		for (const auto e : count_collection)
			output_collection.push_back(make_pair(e.first, e.second));
	}
	/**
	@brief 標準入力関数
	@note
	 標準入力から入力されたsize個の値をcollectionに格納する
	**/
	template<typename T> static void InputStream(vector<T>& collection, int size)
	{
		for (int i = 0; i < size; i++)
			cin >> collection[i];
	}
	/**
	@brief pairの引数を反転させる関数
	@note
	 input_collectionのpair.firstとpair.secondを入れ替えて新たなコンテナを作成する。
	**/
	template<typename T, typename U> static void TurnPair(const vector<pair<T, U>>& input_collection, vector<pair<U, T>>& output_collection)
	{
		for (const auto& e : input_collection)
			output_collection.push_back(make_pair(e.second, e.first));
	}
	/**
	@brief 最大値取得関数
	@note
	 collectionの要素の中で最大値を取得する
	**/
	template<typename T> static T Max(const vector<T>& collection)
	{
		T max = collection[0];
		for (const auto& e : collection)
		{
			if (max < e)
				max = e;
		}
		return max;
	}
	/**
	@brief 最小値取得関数
	@note
	 collectionの要素の中で最大値を取得する
	**/
	template<typename T> static T Min(const vector<T>& collection)
	{
		T min = collection[0];
		for (const auto& e : collection)
		{
			if (e < min)
				min = e;
		}
		return min;
	}
	/**
	@brief 合計関数
	@note
	 collectionの要素を合計して返す(範囲はstart_index以上end_index未満)
	**/
	template<typename T> static T Sum(const vector<T>& collection, int start_index, int end_index)
	{
		int sum = 0;
		for (int i = start_index; i < end_index; i++)
			sum += collection[i];
		return sum;
	}
};

long SumMethodQ1(vector<pair<int, int>>& collection)
{
	long sum = 0;
	seloop(i, 1, collection.size())
		sum += get<0>(collection[i]);
	return sum;
}

long SumMethodQ2(vector<pair<int, int>>& collection)
{
	long sum = 0;
	sum += get<0>(collection[0]);
	seloop(i, 2, collection.size())
		sum += get<0>(collection[i]);
	return sum;

}

long Sum(vector<pair<int, int>>& collection, int min_index, int max_index)
{
	long sum = 0;
	for (int i = min_index; i < max_index; i++)
		sum += get<0>(collection[i]);
	return sum;
}

int main()
{
	int n; cin >> n;
	vector<int> odd_collection(n / 2, 0), even_collection(n / 2, 0);

	loop(i, n / 2)
	{	// 偶数番目と奇数番目の入力を保存
		cin >> odd_collection[i];
		cin >> even_collection[i];
	}

	// 偶数数列の同じ要素をカウントする
	vector<pair<int, int>> count_result;			// p.first=value, p.second=size
	NyaGadgetVector::CountValue<int>(odd_collection, count_result);
	vector<pair<int, int>> count_odd_collection;	// p.first=size, p.second=value
	NyaGadgetVector::TurnPair(count_result, count_odd_collection);
	sort(count_odd_collection.begin(), count_odd_collection.end(), std::greater<int>());

	// 奇数数列の同じ要素をカウントする
	count_result.clear();							// p.first=value, p.second=size
	NyaGadgetVector::CountValue<int>(even_collection, count_result);
	vector<pair<int, int>> count_even_collection;	// p.first=size, p.second=value
	NyaGadgetVector::TurnPair(count_result, count_even_collection);
	sort(count_even_collection.begin(), count_even_collection.end(), std::greater<int>());

	long min = 0;
	// 例外処理その１「偶数数列と奇数数列が全て同じ数字のとき」
	// 数列を個別に見れば置き換え回数はゼロだが、実際は片方の数列を全て置き換える必要がある
	if (get<0>(count_odd_collection[0]) == get<0>(count_even_collection[0]) &&
		get<1>(count_odd_collection[0]) == get<1>(count_even_collection[0]))
	{
		min = n / 2;
		cout << min;
		return 0;
	}

	if (get<1>(count_odd_collection[0]) == get<1>(count_even_collection[0]))
	{	// 例外処理その２「偶数数列と奇数数列で出現頻度が最も高い数字が同じ時」
		if (get<0>(count_odd_collection[1]) < get<0>(count_even_collection[1]))
		{
			min += Sum(count_odd_collection, 1, (int)count_odd_collection.size());
			min += get<0>(count_even_collection[0]);
			min += Sum(count_even_collection, 2, (int)count_even_collection.size());
		}
		else
		{
			min += get<0>(count_odd_collection[0]);
			min += Sum(count_odd_collection, 2, (int)count_odd_collection.size());
			min += Sum(count_even_collection, 1, (int)count_even_collection.size());

		}
		cout << min;
		return 0;
	}

	// 通常処理　出現頻度が最も高い数字に置き換えれば答えになる
	min += Sum(count_odd_collection, 1, (int)count_odd_collection.size());
	min += Sum(count_even_collection, 1, (int)count_even_collection.size());
	cout << min;

	return 0;
}


Compiler output:
In file included from /usr/include/c++/14/bits/stl_algobase.h:71,
                 from /usr/include/c++/14/algorithm:60,
                 from a.cc:1:
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Iterator2 = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Compare = std::greater<int>]':
/usr/include/c++/14/bits/stl_algo.h:1777:14:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
 1777 |           if (__comp(__i, __first))
      |               ~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
 1817 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1908:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
 1908 |           std::__final_insertion_sort(__first, __last, __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4805:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = greater<int>]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:179:6:   required from here
  179 |         sort(count_odd_collection.begin(), count_odd_collection.end(), std::greater<int>());
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h:158:30: error: no match for call to '(std::greater<int>) (std::pair<int, int>&, std::pair<int, int>&)'
  158 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/string:49,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:3:
/usr/include/c++/14/bits/stl_function.h:394:7: note: candidate: 'constexpr bool std::greater<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = int]'
  394 |       operator()(const _Tp& __x, const _Tp& __y) const
      |       ^~~~~~~~
/usr/include/c++/14/bits/stl_function.h:394:29: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'const int&'
  394 |       operator()(const _Tp& __x, const _Tp& __y) const
      |                  ~~~~~~~~~~~^~~
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = std::pair<int, int>; _Iterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Compare = std::greater<int>]':
/usr/include/c++/14/bits/stl_algo.h:1757:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Val_comp_iter<greater<int> >]'
 1757 |       while (__comp(__val, __next))
      |              ~~~~~~^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1785:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
 1785 |             std::__unguarded_linear_insert(__i,
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
 1786 |                                 __gnu_cxx::__ops::__val_comp_iter(__comp));
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
 1817 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1908:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
 1908 |           std::__final_insertion_sort(__first, __last, __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4805:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = greater<int>]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:179:6:   required from here
  179 |         sort(count_odd_collection.begin(), count_odd_collection.end(), std::greater<int>());
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h:240:30: error: no match for call to '(std::greater<int>) (std::pair<int, int>&, std::pair<int, int>&)'
  240 |         { return bool(_M_comp(__val, *__it)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_function.h:394:7: note: candidate: 'constexpr bool std::greater<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = int]'
  394 |       operator()(const _Tp& __x, const _Tp& __y) const
      |       ^~~~~~~~
/usr/include/c++/14/bits/stl_function.h:394:29: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'const int&'
  394 |       operator()(const _Tp& __x, const _Tp& __y) const
      |                  ~~~~~~~~~~~^~~
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Value = std::pair<int, int>; _Compare = std::greater<int>]':
/usr/include/c++/14/bits/stl_heap.h:140:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Distance = long int; _Tp = pair<int, int>; _Compare = __gnu_cxx::__ops::_Iter_comp_val<greater<int> >]'
  140 |       while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
      |                                          ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:247:23:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Distance = long int; _Tp = pair<int, int>; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
  247 |       std::__push_heap(__first, __holeIndex, __topIndex,
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  248 |                        _GLIBCXX_MOVE(__value), __cmp);
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:356:22:   required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
  356 |           std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
      |           ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  357 |                              __comp);
      |                              ~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1593:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
 1593 |       std::__make_heap(__first, __middle, __comp);
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1868:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
 1868 |       std::__heap_select(__first, __middle, __last, __comp);
      |       ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1884:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _Ra