fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <iostream>
  3. #include <algorithm>
  4. #define ll long long;
  5. const int maxn = 2e5 + 5;
  6. using namespace std;
  7. void AlShafii()
  8. {
  9. 	ios_base::sync_with_stdio(false);
  10. 	cin.tie(NULL);
  11. 	cout.tie(NULL);
  12.  
  13. }
  14. // make simmler chars together like abab be like aabb or baab
  15. int main()
  16. {
  17. 	AlShafii();
  18. 	int t;
  19. 	cin >> t;
  20. 	while (t--)
  21. 	{
  22. 		int n;
  23. 		cin >> n;
  24. 		string s;
  25. 		cin >> s;
  26. 		int count = 0;
  27. 		int pos[maxn];
  28. 		for (int i = 0; i < n; i++)
  29. 		{
  30. 			if (s[i] == 'a')
  31. 			{
  32. 				pos[count] = i;
  33. 				count++;
  34. 			}
  35. 		}
  36. 		long long coasta = 0;
  37. 		if (count > 0)
  38. 		{
  39. 			int midi = count / 2;
  40. 			int tar = pos[midi] - midi;
  41. 			for (int i = 0; i < count; i++)
  42. 			{
  43. 				int x = pos[i] - i;
  44. 				coasta += abs(x - tar);
  45. 			}
  46.  
  47. 		}
  48. 		count = 0;
  49. 		for (int i = 0; i < n; i++)
  50. 		{
  51. 			if (s[i] == 'b')
  52. 			{
  53. 				pos[count] = i;
  54. 				count++;
  55. 			}
  56. 		}
  57. 		long long costb = 0;
  58. 		if (count > 0)
  59. 		{
  60. 			int midi = count / 2;
  61. 			int tar = pos[midi] - midi;
  62. 			for (int i = 0; i < count; i++)
  63. 			{
  64. 				int x = pos[i] - i;
  65. 				costb += abs(x - tar);
  66. 			}
  67. 		}
  68. 		cout << min(coasta, costb) << endl;
  69.  
  70.  
  71.  
  72.  
  73.  
  74.  
  75. 	}
  76. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fvJZsL
language:
C++14 (clang 8.0)
created:
12 hours ago
visibility:
public

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!