swap adjacent positions and the first thing that comes to mind is inversions!
think bubble sort, = reverse exchange for strong> the number of the original string position can be seen as an ordered sequence, such as
a aa z a
1, 2, 3, 4, 5
after reverse sequence is:
a to z a aa
for each location should choose the original series more the front of the plane, so to reverse contribution to the smallest reason should be:
1 2 3 4 5
o problem can be converted to reverse the number!
#include<iostream>
#include<vector>
#define pb push_back
typedef long long ll;
using namespace std;
const int N = 2e5 + 5;
char s[N];
ll n,a[N],b[N];
vector<ll> v[26];
int pos[26];
ll merge(int l,int r){
ll ans = 0;
if(l >= r){
return 0;
}
int mid = (l + r)>>1;
ans += merge(l,mid);
ans += merge(mid + 1,r);
int i = l,j = mid + 1,k = 0;
while(i<=mid && j <= r){
if(a[i] <= a[j]){
b[++k] = a[i++];
ans+= j - mid - 1;
}
else
b[++k] = a[j++];
}
while(i <= mid)b[++k] = a[i++],ans += r - mid;
while(j <= r)b[++k] = a[j++];
for(i = l;i <= r;i++)
a[i] = b[i - l + 1];
return ans;
}
int main(){
cin>>n;
cin>>(s + 1);
for(int i = 1;i <= n;i++)v[s[i] - 'a'].pb(i);
int j = 0;
for(int i = n;i>=1;i--){
a[++j] = v[s[i] - 'a'][pos[s[i] - 'a']++];
}
cout<<merge(1,n)<<endl;
cout<<endl;
return 0;
}
div>
Read More:
- Vector delete pop of element_ back(),erase(),remove()
- The 11th Zhejiang Provincial Collegiate Programming Contest
- error: `cout’ was not declared in this scope
- 1143 Lowest Common Ancestor
- Reverse function: reverses container contents
- “Error: ` cout ‘was not declared in this scope”
- The usage and difference of atoi() and stoi() functions in C + +
- error C2065: ‘cout’ : undeclared identifier
- C++:error C2228: left of ‘.str’ must have class/struct/union
- CIN in C + + cin.get ()、 cin.getline (), getline(), gets() function
- C++ foundation — clear/erase/pop of string class_back
- Finding the longest connection path of a string
- The use of C + + template function and lambda expression
- Conversion from hexadecimal to decimal
- P – Random Teams
- SFINAE of C++ idioms
- C / C + + rounding function ceil(), floor ()
- Error in comparing the size function of STL with negative number
- Various errors (c + +)
- Problem solving – vs debugging window flash solution