洛谷P3531 [POI2012]LIT-Letters

题目描述

Little Johnny has a very long surname.

Yet he is not the only such person in his milieu.

As it turns out, one of his friends from kindergarten, Mary, has a surname of the same length, though different from Johnny's.

Moreover, their surnames contain precisely the same number of letters of each kind - the same number of letters A, same of letters B, and so on.

Johnny and Mary took to one another and now often play together.

One of their favourite games is to gather a large number of small pieces of paper, write successive letters of Johnny's surname on them, and then shift them so that they obtain Mary's surname in the end.

Since Johnny loves puzzles, he has begun to wonder how many swaps of adjacent letters are necessary to turn his surname into Mary's. For a child his age, answering such question is a formidable task.

Therefore, soon he has asked you, the most skilled programmer in the kindergarten, to write a program that will help him.

给出两个长度相同且由大写英文字母组成的字符串A、B,保证A和B中每种字母出现的次数相同。

现在每次可以交换A中相邻两个字符,求最少需要交换多少次可以使得A变成B。

输入输出格式

输入格式:

In the first line of the standard input there is a single integer n(2<=n<=1000000) denoting the length of Johnny's surname.

The second line contains Johnny's surname itself, i.e., contains its n successive letters (without spaces).

The third line contains Mary's surname in the same format: a string of n letters (with no spaces either).

Both strings consist only of capital (upper-case) letters of the English alphabet.

In tests worth 30% of points it additionally holds that n<=1000

输出格式:

Your program should print a single integer to the standard output: the minimum number of swaps of adjacent letters that transforms Johnny's surname into Mary's.

输入输出样例

输入样例#1:

3
ABC
BCA

输出样例#1: 

2

说明

给出两个长度相同且由大写英文字母组成的字符串A、B,保证A和B中每种字母出现的次数相同。

现在每次可以交换A中相邻两个字符,求最少需要交换多少次可以使得A变成B。

我们可以先考虑一下小的数据范围

如果只有A B两个字母

那么只有两种情况

  1. A B \nA B 对于这种情况我们是不用进行交换的
  2. A B \nB A 这种情况只需交换一次即可

为了方便讨论,我们把 A B按照顺序标号为1 2

那么第二种情况就是

1 2

2 1 此时2在1前,且2比1大(这不是废话么。。)

那么我们不难就会想到:逆序对

如果不放心,可以自己验证几组数据,意会一下就很明确了

现在就有两个问题:

一.逆序对怎么求

1.暴力,绝对TLE

2.归并排序

3.树状数组

二.怎么维护出现的顺序

楼下的那位大佬是用的类似于邻接表的一个东西,蒟蒻表示看不懂,,,,

我们不难发现这个位置是满足先进先标顺序的

那么开26个队列来维护就好了23333

另外

不开long long见祖宗!!!

多年oi一场空!!!!!!

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<deque>
 7 #include<queue>
 8 #define LL long long 
 9 #define lb(x)    ((x)&(-x))
10 using namespace std;
11 const int MAXN=40000001;
12 inline int read()
13 {
14     char c=getchar();int x=0,f=1;
15     while(c<'0'||c>'9')    {if(c=='-')    f=-1;c=getchar();}
16     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*f;
17 }
18 int n;
19 queue<int>q[28];
20 int a[MAXN];
21 int tree[MAXN];
22 inline void Point_Add(int pos,int val)
23 {
24     while(pos<=n)
25     {
26         tree[pos]+=val;
27         pos+=lb(pos);
28     }
29 }
30 inline int Interval_Sum(int pos)
31 {
32     int ans=0;
33     while(pos)
34     {
35         ans+=tree[pos];
36         pos-=lb(pos);
37     }
38     return ans;
39 }
40 int main()
41 {
42     n=read();
43     for(int i=1;i<=n;i++)
44     {
45         char c=getchar();
46         q[c-'A'].push(i);
47     }
48     char c=getchar();// 可恶的换行符 
49     for(int i=1;i<=n;i++)
50     {
51         char c=getchar();
52         a[i]=q[c-'A'].front();
53         q[c-'A'].pop();
54     }
55     LL ans=0;
56     for(int i=1;i<=n;i++)
57     {
58         Point_Add(a[i],1);
59         ans+=i-Interval_Sum(a[i]);// 树状数组求逆序对,不懂的自行百度 
60     }
61     printf("%lld",ans);
62     return 0;
63 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

深入剖析Go语言编程中switch语句的使用

switch语句可以让一个变量对反对值的列表平等进行测试。每个值被称为一个的情况(case),变量被接通检查每个开关盒(switch case)。 在Go编程,...

37070
来自专栏Golang语言社区

Go语言struct类型详解

struct Go语言中,也和C或者其他语言一样,我们可以声明新的类型,作为其它类型的属性或字段的容器。例如,我们可以创建一个自定义类型person代表一个人的...

30470
来自专栏和蔼的张星的图像处理专栏

35. 翻转链表

样例 给出一个链表1->2->3->null,这个翻转后的链表为3->2->1->null

29030
来自专栏公众号_薛勤的博客

详解JSOUP的Select选择器语法

可以使用Element.select(String selector) 和 Elements.select(String selector) 方法实现:

11120
来自专栏nummy

jQuery串联操作

把与表达式匹配的元素添加到jQuery对象中。这个函数可以用于连接分别与两个表达式匹配的元素结果集。

6110
来自专栏Pythonista

Golang之接口(interface)

 //Golang中的接口,不需要显示的实现。只要一个变量,含有接口类型中的所有方法,那么这个变量就实现了这个接口。

41130
来自专栏Golang语言社区

浅谈Go语言中的结构体struct &amp; 接口Interface &amp; 反射

结构体struct struct 用来自定义复杂数据结构,可以包含多个字段(属性),可以嵌套;

24340
来自专栏Golang语言社区

Go语言struct类型详解

struct Go语言中,也和C或者其他语言一样,我们可以声明新的类型,作为其它类型的属性或字段的容器。例如,我们可以创建一个自定义类型person代表一个人的...

28840
来自专栏流柯技术学院

Java Selenium封装--RemoteWebElement

26720
来自专栏五分钟学算法

每天一算:Remove Linked List Elements

LeetCode上第203号问题:Remove Linked List Elements

8730

扫码关注云+社区

领取腾讯云代金券