アルファベット交換
3642 ワード
アルファベット交換
ある正教授級の特教師は古い文字を獲得し、すべて26個の大文字の英語のアルファベットグループの大文字の英語のアルファベットから構成されている.彼は狂った考えを生んだ.この文字の中のすべての母をAからZの順序で並べ替えた.つまり、すべての順序、つまりすべてのAを先頭に置いて、それからすべてのBについて、すべてのC、最後にすべてのZだった.例えば、元の文字列が「HELLOWORLD」であり、ソート後に「DEHLLLOORW」となる.しかし、特教は結局国務院の特殊手当を受け取っているので、並べ替えのたびに隣接する2つの字しか交換できないという要求がある.隣接する2つの字しか交換できない.毎回隣接する2つの字しか交換できない.毎回隣接する2つの字しか交換できない.毎回隣接する2つの文字しか交換できない.今彼は最低何回交換すれば交換が完了するか知りたいと思っています.
この問題は一目で逆序を求めることがわかる.どうでもいい
ある正教授級の特教師は古い文字を獲得し、すべて26個の大文字の英語のアルファベットグループの大文字の英語のアルファベットから構成されている.彼は狂った考えを生んだ.この文字の中のすべての母をAからZの順序で並べ替えた.つまり、すべての順序、つまりすべてのAを先頭に置いて、それからすべてのBについて、すべてのC、最後にすべてのZだった.例えば、元の文字列が「HELLOWORLD」であり、ソート後に「DEHLLLOORW」となる.しかし、特教は結局国務院の特殊手当を受け取っているので、並べ替えのたびに隣接する2つの字しか交換できないという要求がある.隣接する2つの字しか交換できない.毎回隣接する2つの字しか交換できない.毎回隣接する2つの字しか交換できない.毎回隣接する2つの文字しか交換できない.今彼は最低何回交換すれば交換が完了するか知りたいと思っています.
この問題は一目で逆序を求めることがわかる.どうでもいい
#include
#include
#include
using namespace std;
int e[2000010],tmp1[2000010];
long long ans;
void merge(int left, int mid, int right)
{
int i=left, j=mid+1, k=left;
while (i<=mid && j<=right) {
if (e[i]<=e[j]) {
tmp1[k++] = e[i++];
} else {
tmp1[k++] = e[j++];
ans = ans+mid-i+1;
}
}
while (i<=mid) tmp1[k++] = e[i++];
while (j<=right)tmp1[k++] =e[j++];
memcpy(&e[left], &tmp1[left], (right-left+1)*sizeof(int));
}
void merge_sort(int left, int right)
{
if (left<right)
{
int mid=(left+right)>>1;
merge_sort(left, mid);
merge_sort(mid+1, right);
merge(left, mid, right);
}
}
int main()
{
freopen("swapping.in","r",stdin);
freopen("swapping.out","w",stdout);
char s;
int k=0;
while (cin>>s)
{
k++;
e[k]=s-48;
}
merge_sort(1,k);
cout<