Counting Liars

题目描述

奶牛 Bessie 正藏在数轴上的某个位置。农夫 John 的另外 $N$ 头奶牛（$1\le N\le 1000$）各自提供一条信息：第 $i$ 头奶牛要么说 Bessie 藏在某个小于等于 $p_i$ 的位置，要么说 Bessie 藏在某个大于等于 $p_i$ 的位置（$0\le p_i\le 10^9$）。 不幸的是，可能不存在一个藏身位置能够与所有奶牛的说法都一致，这意味着并非所有奶牛都在说真话。请计算最少有多少头奶牛一定是在说谎。

输入格式

第一行包含 $N$。 接下来的 $N$ 行每行包含一个字符 L 或 G，后跟一个整数 $p_i$。L 表示第 $i$ 头奶牛说 Bessie 的藏身位置小于等于 $p_i$；G 表示第 $i$ 头奶牛说 Bessie 的藏身位置大于等于 $p_i$。

输出格式

输出最少必须说谎的奶牛数量。

2
G 3
L 5

0

2
G 3
L 2

1

提示

可能没有任何奶牛在说谎。 至少有一头奶牛必须在说谎。 题目贡献：Jesse Choe

标签: USACO|2022|Bronze

来源

USACO|2022|Bronze