# 洛谷 3029 [USACO11NOV]牛的阵容Cow Lineup

2021年09月15日 阅读数：3

## 题目描述

Farmer John has hired a professional photographer to take a picture of some of his cows. Since FJ's cows represent a variety of different breeds, he would like the photo to contain at least one cow from each distinct breed present in his herd.node

FJ's N cows are all standing at various positions along a line, each described by an integer position (i.e., its x coordinate) as well as an integer breed ID. FJ plans to take a photograph of a contiguous range of cows along the line. The cost of this photograph is equal its size -- that is, the difference between the maximum and minimum x coordinates of the cows in the range of the photograph.ios

Please help FJ by computing the minimum cost of a photograph in which there is at least one cow of each distinct breed appearing in FJ's herd.app

## 输入输出格式

• Line 1: The number of cows, N (1 <= N <= 50,000).this

• Lines 2..1+N: Each line contains two space-separated positive integers specifying the x coordinate and breed ID of a single cow. Both numbers are at most 1 billion.

• Line 1: The smallest cost of a photograph containing each distinct breed ID.

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

```4
```

## 说明

There are 6 cows, at positions 25,26,15,22,20,30, with respective breed IDs 7,1,1,3,1,1.队列

The range from x=22 up through x=26 (of total size 4) contains each of the distinct breed IDs 1, 3, and 7 represented in FJ's herd.ci

```#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int n;
long long ans=2e15;
struct node
{
int pos,bl;
bool operator < (node p)const
{
return pos<p.pos;
}
}e[50001];
int hassh[50001],sum[50001],cnt;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&e[i].pos,&e[i].bl),hassh[i]=e[i].bl;
sort(hassh+1,hassh+n+1);
int tot=unique(hassh+1,hassh+n+1)-(hassh+1);
for(int i=1;i<=n;i++) e[i].bl=lower_bound(hassh+1,hassh+n+1,e[i].bl)-hassh;
sort(e+1,e+n+1);
for(int i=1;i<=n;i++)
{

if(++sum[e[i].bl]==1) cnt++;
que[tail++]=i;