[字符串]Cities and States-S
题面题目描述输入输出
解题思路
O
(
N
2
)
O(N^2)
O(N2)思路
O
(
N
2
)
O(N^2)
O(N2)优化核心代码
O
(
N
)
O(N)
O(N)做法核心代码
题面
题目描述
为了促进奶牛的智力发展，
F
a
r
m
e
r
J
o
h
n
Farmer John
FarmerJohn在牛棚的墙上放置了一幅很大的美国地图。在奶牛们花费很多时间研究地图后，他们注意到一个奇特的现象。 例如，有这样两个城市：弗林特
(
F
l
i
n
t
)
(Flint)
(Flint)，其州代码为
M
I
MI
MI，和迈阿密
(
M
i
a
m
i
)
(Miami)
(Miami)，州代码为
F
L
FL
FL，他们之间存在一个特殊的关系："弗林特"
(
F
l
i
n
t
)
(Flint)
(Flint)的前两个字母刚好是迈阿密的州代码
(
F
L
)
(FL)
(FL)，同时迈阿密
(
M
i
a
m
i
)
(Miami)
(Miami)前两个字母也刚好是弗林特的州代码
(
M
I
)
(MI)
(MI)。 如果两个来自不同州的城市满足这一属性，那我们就说这两个城市是特殊的一对。奶牛们想知道有多少对这样的城市存在。请帮助他们解决这个有趣的地理难题！
输入
第 1 行输入地图上城市的个数
N
N
N； 接下去的
N
N
N 行，每行分别输入两个字符串。第一个表示城市名称(字符串由大写英文字母组成， 最少两 个，最多不能超过
10
10
10 个)，第二个表示该城市的州代码(两个大写字母)。多个城市的名称允许相同，但 他们必须属于不同的州。
输出
输出共一行一个整数，满足条件的特殊城市对数。
解题思路
O
(
N
2
)
O(N^2)
O(N2)思路
N
2
N^2
N2枚举判断，做法显然
O
(
N
2
)
O(N^2)
O(N2)优化
以城市名为第一关键字，州代码为第二关键字排序 搜索到有匹配的，若继续搜索不匹配的，便弹出
核心代码
sort(str
+1,str
+1+N
,cmp
);
sort(str
+1,str
+1+N
,cmp2
);
for(register int i
=1; i
<=N
; i
++) {
for(register int j
=i
+1; j
<=N
; j
++) {
if(str
[i
].x
==str
[j
].y
) {
for(register int k
=j
; k
<=N
; k
++) {
if(str
[k
].x
==str
[i
].y
)ans
++;
if(str
[i
].x
!=str
[j
].y
)break;
}
break;
}
}
}
O
(
N
)
O(N)
O(N)做法
先将字符串转换成数字 cin>>s; str[i].x=(s[0]-'A')*26+(s[1]-'A'); cin>>s; str[i].y=(s[0]-'A')*26+(s[1]-'A'); 在前面
O
(
N
2
)
O(N^2)
O(N2)优化的基础上提前处理数组
a
a
a
a
i
a_i
ai的定义是州代码为
i
i
i的第一个城市所在的位置
核心代码
bool cmp(const _str
&a1
,const _str
&a2
) {
return a1
.y
<a2
.y
;
}
bool cmp2(const _str
&a1
,const _str
&a2
) {
return a1
.x
<a2
.x
;
}
scanf("%d",&N
);
for(int i
=1; i
<=N
; i
++) {
cin
>>s
;
str
[i
].x
=(s
[0]-'A')*26+(s
[1]-'A');
cin
>>s
;
str
[i
].y
=(s
[0]-'A')*26+(s
[1]-'A');
}
sort(str
+1,str
+1+N
,cmp2
);
sort(str
+1,str
+1+N
,cmp
);
for(register int i
=1; i
<=N
; i
++) {
if(a
[str
[i
].y
]==0) {
a
[str
[i
].y
]=i
;
}
}
for(register int i
=1; i
<=N
; i
++) {
for(register int k
=a
[str
[i
].x
]; k
<=N
; k
++) {
if(k
<=i
)break;
if(str
[i
].x
!=str
[k
].y
)break;
if(str
[k
].x
==str
[i
].y
)ans
++;
}
}
