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

2021年09月15日 阅读数:3
这篇文章主要向大家介绍洛谷 3029 [USACO11NOV]牛的阵容Cow Lineup,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

https://www.luogu.org/problem/show?pid=3029

题目描述

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

依次给出N头牛的位置及种类,要求找出连续一段,使其中包含全部种类的牛,问:这连续的一段最小长度是多少?ssh

输入输出格式

输入格式:ide

 

  • 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.

 

输出格式:spa

 

  • 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 
输出样例#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

感谢 wjcwinmt 提供题目简述get

 

队列

#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 head,tail,que[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;
        while(head<tail && sum[e[que[head]].bl]>1) sum[e[que[head++]].bl]--;
        if(cnt==tot) ans=min(ans,1ll*e[que[tail-1]].pos-e[que[head]].pos);
    }
    cout<<ans;
}
做者: xxy
本文版权归做者全部,转载请用连接,请勿原文转载,Thanks♪(・ω・)ノ。