fork(5) download
copy 
  1. #include <iostream>
  2. #include <map>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <set>
  6. using namespace std;
  7. map<int, int> mp;
  8. map<int, int>::iterator it;
  9. vector<pair<int, int> > v;
  10. multiset<int> x;
  11. multiset<int>::iterator it1, it2;
  12.  
  13. bool cmp(const pair<int, int> &a, pair<int, int> &b)
  14. {
  15. 	return a.second<b.second;
  16. }
  17.  
  18. int main() {
  19. 	int T, N, p, i, j;
  20. 	cin>>T;
  21. 	while(T--)
  22. 	{
  23. 		cin>>N;
  24. 		int ans=0;
  25. 		while(N--)
  26. 		{
  27. 			cin>>p;
  28. 			mp[p]++;
  29. 		}
  30. 		for(it=mp.begin(); it!=mp.end(); ++it)
  31. 			x.insert(it->second);
  32. 		while((int)x.size()!=1)
  33. 		{
  34. 			it1=x.end();
  35. 			it1--;
  36. 			j=*it1;
  37. 			it2=it1;
  38. 			it2--;
  39. 			x.erase(it1);
  40. 			int m=*it2;
  41. 			ans+=m;
  42. 			x.erase(it2);
  43. 			x.insert(j-m);
  44. 			/*for(it1=x.begin(); it1!=x.end(); ++it1)
  45. 				cout<<*it1<<" ";
  46. 			cout<<endl;*/
  47. 		}
  48. 		//cout<<*x.begin()<<endl;
  49. 		ans+=*x.begin();
  50. 		cout<<ans<<endl;
  51. 		x.clear();
  52. 		mp.clear();
  53. 	}
  54. 	return 0;
  55. }
  56.  
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
1
3
1 2 3
stdout
copy 
2
https://ideone.com/1qkWsn
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!