暑假集训D8 2023.8.1 补题

C. P3029 [USACO11NOV] Cow Lineup S

有 \(n\) 只牛, 他们各自有自己的编号(不同牛的编号可能是相同的).这些牛站在不同的位置.现在需要给这些牛拍一张照.有如下要求

• 选定一个范围内的牛拍照,这些牛需要包含所有出现过的编号
• 照片的成本是这个范围,因此范围越小越好
  已经给定所有牛的位置和编号,请你找出范围的最小值.

这题没什么思路.看题解后发现并不难,而且方法很多.
最简单的方法:
把所有牛的距离按从小到大排序,从左到右遍历.依次把牛加入队列,如果当前的牛的编号已经在队列里有了,并且之前的位置是在队列的最左侧,则将最左侧的牛出队,同时更新 \(l\) 的值.然后记录队列中已有的牛的不同编号的个数.如果包含所有编号数则就可以更新答案.注意这题用数组记录是否有某编号的牛会 \(RE\) 三个点,改成 \(map\) 就好了,说实话有点坑....如果是比赛还真不一定想得到.
找最左侧的牛也非常简单,只要用优先队列即可..

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#define endl '\n'
#define pb push_back
using namespace std;
typedef pair<int,int> PII;
const int N = 2e6+10;
PII a[N];
int m;
map<int,int> vis;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i].first>>a[i].second;
		if(!vis[a[i].second])
		{
			m++;
			vis[a[i].second]= 1;
		}
	}
	vis.clear();
	sort(a,a+n);
	int res = 2147483647;
	priority_queue<PII,vector<PII>,greater<PII> > q;
	q.push(a[0]);
	vis[a[0].second] =1;
	int i = 1;
	int cnt = 1;
	int l = a[0].first;
	while(i<n)
	{
		q.push(a[i]);
		if(!vis[a[i].second])
		{
			cnt++;
		}

		vis[a[i].second] ++;
		PII t = q.top();
		if(vis[t.second]>1)
		{
			q.pop();
			l = q.top().first;
			vis[t.second]--;
		}
		if(cnt==m)
		{
			res = min (res,a[i].first - l); 
		}
		i++;
	}
	cout<<res<<endl;
	return 0;
}