USACO2014OPEN 铜组第二题

题目描述

农夫约翰（Farmer John）的 ( N ) 头奶牛（( 1 <= N <= 100,000 ) ）站在一条一维围栏的不同位置。第 ( i ) 头奶牛的位置是 ( x_i )（范围 ( 0 ) 到 ( 1,000,000,000 ) ），品种是 G（根西牛）或 H（荷斯坦牛）。任意两头奶牛位置不同。

FJ 想拍摄一张连续区间内的奶牛照片用于县 fair，但要求照片中的奶牛品种“公平呈现”：对于照片中出现的所有品种，每种品种的数量必须相等。例如，一张包含 27 头荷斯坦牛和 27 根西牛的照片是公平的；但包含 10 头荷斯坦牛和 9 根西牛的照片则不公平。

照片的“尺寸”定义为照片中奶牛最大位置与最小位置的差值。请帮助 FJ 找出满足条件的最大照片尺寸；如果无法满足（比如所有奶牛品种都不同，或无法找到数量相等的组合 ），则可能拍摄单头奶牛的照片（尺寸为 0 ）。

输入格式

• 第 1 行：整数 ( N )（奶牛数量 ）。
• 第 2 至 ( N+1 ) 行：每行包含整数 ( x_i ) 和字符 ( b_i )（G 或 H ），描述第 ( i ) 头奶牛的位置和品种。

样例输入

6
4 G
10 H
7 G
16 G
1 G
3 H

输入详情
6 头奶牛，按位置从左到右排序后的品种依次是：G, H, G, G, H, G（需注意输入顺序不代表位置顺序，实际要先按位置排序处理 ）。

输出格式

输出 1 行，为满足条件的最大照片尺寸。

样例输出

7

输出详情
最大公平照片包含中间 4 头奶牛,其中有 2 头荷斯坦牛（H）和 2 根西牛（G），尺寸为 ( 最大位置 - 最小位置 = 7 )（具体需按排序后的位置计算 ）。