题目大意:找最小包含所有牛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; }