USACO2014DEC 铜组第四题

题目描述

农夫约翰（Farmer John）一直在研究机器学习领域，想通过分析数据发现规律。他用农场现有奶牛的数据，构建了一个“最近邻分类器”，用于预测新奶牛是否有斑点。

分类规则如下：
对于一头体重为 ( C ) 的新奶牛，找到现有奶牛中体重最接近 ( C ) 的奶牛 ( C' )（若有多个，任选其一 ）。

• 若 ( C' ) 有斑点（标记 S ），则预测新奶牛有斑点。
• 若 ( C' ) 无斑点（标记 NS ），则预测新奶牛无斑点。
• 若存在两个不同体重的奶牛 ( C_1 ) 和 ( C_2 )，与 ( C ) 的距离相等且是最近距离（即 ( |C - C_1| = |C - C_2| ) 且是最小值 ），则：
  • 若 ( C_1 ) 或 ( C_2 ) 有斑点，预测新奶牛有斑点；
  • 否则（两者都无斑点 ），预测无斑点。

现有 ( N ) 头奶牛的数据（( 1 <= N <= 50,000 ) ），以及新到的一批奶牛（体重覆盖区间 ([A, B]) 的所有整数，( 1 <= A <= B <= 1,000,000,000 ) ）。请计算这些新奶牛中，被预测为“有斑点”的数量。

输入格式

• 第 1 行：三个整数 ( N )、( A )、( B )，分别表示现有奶牛数量、新奶牛体重的起始和结束值。
• 第 2 至 ( N+1 ) 行：每行描述一头现有奶牛，格式为 S W（有斑点，体重 ( W ) ）或 NS W（无斑点，体重 ( W ) ）。

样例输入

3 1 10
S 10
NS 4
S 1

输入详情

• 现有 3 头奶牛：
  • 有斑点，体重 10；
  • 无斑点，体重 4；
  • 有斑点，体重 1。
• 新奶牛体重覆盖 ( 1 \sim 10 ) 的所有整数。

输出格式

输出 1 行，为新奶牛中被预测为“有斑点”的数量。

样例输出

6

输出详情
新奶牛体重 1~10 中，被预测为有斑点的是 1、2、7、8、9、10，共 6 头。