[USACO11NOV] 奶牛排队 S

题目描述

农夫约翰请了一位专业摄影师，准备给他的部分奶牛拍一张照片。 由于约翰的奶牛分属多个不同品种，他希望照片里每种出现过的品种都至少有一头奶牛入镜。

约翰的 N 头奶牛都站在一条直线上的不同位置，每头奶牛都用一个整数坐标（即 x 坐标）和一个整数品种编号来表示。 约翰打算拍摄直线上一段连续区间内的奶牛。 拍摄的成本等于区间长度——也就是区间内所有奶牛的最大 x 坐标减去最小 x 坐标。

请你帮约翰计算：能拍到所有品种奶牛的照片的最小成本。

输入格式

• 第 1 行：奶牛数量 N（1 ≤ N ≤ 50,000）
• 第 2~N+1 行：每行两个用空格分隔的正整数，分别表示一头奶牛的 x 坐标和品种编号 两个数值最大都可达 10 亿

输出格式

• 第 1 行：一个整数，表示包含所有品种奶牛的照片的最小成本

输入样例 1：

6 
25 7 
26 1 
15 1 
22 3 
20 1 
30 1 

输出样例 1：

4

提示

共有 6 头奶牛，坐标分别是 25、26、15、22、20、30，对应品种编号：7、1、1、3、1、1。

从 x=22 到 x=26 的区间（总成本 4）包含了所有品种：1、3、7，满足要求。

标签: P3029|2011|USACO|离散化|队列|双指针 two-pointer

来源

P3029|[USACO11NOV] Cow Lineup S