USACO11NOV 牛的阵容

wjh15101051's space

卧薪尝胆，厚积薄发。

USACO11NOV 牛的阵容

Date: Mon Sep 17 19:28:03 CST 2018

In Category: NoCategory

Description：

给出每头牛的位置和种类，求一个最小的区间包含所有种类的牛。

$1\le n \le 50000$

Solution：

双指针，保证两个指针之间包含所有种类的牛，维护 $cnt$ 表示第 $i$ 种牛在 $[l,r]$ 中出现了多少次，每次右指针右移判断左指针是否能够右移并修改 $cnt$ 即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

int n;

#define MAXN 50010

#define INF 0x3f3f3f3f

struct cow

{

	int p,id;

}s[MAXN];

bool cmp_p(cow a,cow b){return a.p < b.p;}

int b[MAXN],tot = 0;

map<int,int> fr;

int cnt[MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d",&s[i].p,&s[i].id);

		b[i] = s[i].id;

	}

	sort(s + 1,s + 1 + n,cmp_p);

	sort(b + 1,b + 1 + n);

	for(int i = 1;i <= n;++i)

		if(i == 1 || b[i] != b[i - 1])

			fr[b[i]] = ++tot;

	for(int i = 1;i <= n;++i)

		s[i].id = fr[s[i].id];

	int sum = 0;

	int i,j;

	memset(cnt,0,sizeof(cnt));

	for(i = 1;i <= n;++i)

	{

		++cnt[s[i].id];

		if(cnt[s[i].id] == 1)++sum;

		if(sum == tot)break;

	}

	--cnt[s[i].id];

	int ans = INF;

	for(j = 1;i <= n;++i)

	{

		++cnt[s[i].id];

		while(cnt[s[j].id] != 1)

		{

			--cnt[s[j].id];

			++j;

		}

		ans = min(ans,s[i].p - s[j].p);

	}

	cout << ans << endl;

	return 0;

}

In tag: 技巧-双指针

wjh15101051