牛客假日团队赛57  Cow Lineup题解

链接：https://ac.nowcoder.com/acm/contest/7157/A 来源：牛客网

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.

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. 

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.

输入描述:

* Line 1: The number of cows, N (1 <= N <= 50,000). * 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.

示例1

输入

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.

题目大意：找最小包含所有牛id的区间长度

思路：双指针+二分法

因为题目的区间很大，所以采用双指针优化一下，在判断是否区间内是否找全时使用二分（否则会超时）

代码中又详细的注释

#include<bits/stdc++.h> using namespace std; #define ll long long ll cnt,p[50003],top,bo[100000],b[10000000]; struct node { ll id,po; }; node w[50004]; bool cmp(node a,node b) { return a.po<b.po; } int main() { int m; scanf("%d",&m); memset(bo,0,sizeof(bo)); top=0; for(int i=1; i<=m; ++i) { scanf("%lld%lld",&w[i].po,&w[i].id); p[i-1]=w[i].id; } sort(w+1,w+1+m,cmp);//按坐标升序 sort(p,p+m); top=unique(p,p+m)-p;//将id排序并去重 ll ans=99999999999999999,s=0; for(int l=1,r=0; l<=m; l++)//左指针左移 { for(; s<top&&r<m; r++)//右指针又移 { int x=lower_bound(p,p+top,w[r+1].id)-p;//注意要二分，否则会超时 s+=(++bo[x])==1; //bo数组用来标记牛的编号 } if(s==top) //说明此区间无重复 ans=min(ans,w[r].po-w[l].po); int x=lower_bound(p,p+top,w[l].id)-p; s-=(--bo[x])==0; } printf("%lld\n",ans); return 0; }