「USACO11NOv1」 Cow Lineup S题解

问题描述

农民约翰雇一个专业摄影师给他的部分牛拍照。由于约翰的牛有好多品种，他喜欢他的照片包含每个品种的至少一头牛。

约翰的牛都站在一条沿线的不同地方， 每一头牛由一个整数位置\(X_i\)以及整数品种编号\(ID_i\)表示。

约翰想拍一张照片，这照片由沿线的奶牛的连续范围组成。照片的成本与规模相当，这就意味着，在一系列照片中的最大和最小\(X\)坐标的差距决定了照片的成本。(一个提示)

请帮助约翰计算最小的照片成本，这些照片中有每个不同的品种的至少一头牛，没有两头牛愿意站在同一个地点的。

输入格式

第\(1\)行：牛的数量\(N(1<=N<=50,000)\);

第\(2\)行：每行包含\(2\)个以空格分隔的正整数\(X_i\)和\(ID_i\)；意义如题目描述；

输出格式

输出共一行，包含每个不同品种\(ID\)的照片的最低成本。

分析

因为所有牛都在一条线上，且都有一个不同的坐标(\(X_i\))，所以可以用一个一维数组存，因为\(X_i\)不知道范围，所以用i来定范围方便一些。题目中说了，一头牛有两个信息：\(X_i\)坐标和\(ID_i\)品种，所以用一个结构体数组来存储每一头牛的信息

#define LL long long
struct COW{
    LL x,d;//x是坐标，d是品种，避免爆炸开long long
}cow[50005];

因为输入坐标时是乱的，使用双指针需要一个有序的序列，所以要对它排序，题目中要求在原序列中选取一段区间，所以要用\(X_i\)排序，用map<LL,LL> v1记录\(ID_i\)的头数

#define LL long long
map<LL,LL> v1,v2;//v11的作用后面讲
bool cmp(COW a,COW b){
    return a.x<b.x;
}
scanf("%d",&n);
for (LL i=1;i<=n;++i){
    scanf("%lld %lld",&cow[i].x,&cow[i].d);
    v1[cow[i].d]++;
    v2[cow[i].d]++;
}
sort(cow+1,cow+n+1,cmp);

再看方法，因为要求最少几头牛,且每个品种至少一头，所以就要尽量减少每一个品种的头数，只要每个种类的头数\(>=1\)就可以了，题目中提示：照片的成本与规模相当，这就意味着，在一系列照片中的最大和最小\(X\)坐标的差距决定了照片的成本。所以只要把子序列的左边界(l)和右边界(r)求出来就可以了(就是双指针嘛)

LL l=1,r=n;
while (v1[cow[l].d]!=1){
   v1[cow[l].d]--;
   ++l;
}//缩减左边界
while (v1[cow[r].d]!=1){
   v1[cow[r].d]--;
   --r;
}//缩减右边界
LL first=cow[r].x-cow[l].x;//得到答案

但是，有时先缩减左边界和先缩减右边界得到的答案不一样(你猜我怎么知道的)，所以应该重复一次，避免漏掉更小的情况，得到的两个答案中的最小值就是最终答案，因为v1在第一次缩减就已经变了，第二次没法用了，所以在开头就再设一个v2，给第二次用

LL l=1,r=n;
while (v1[cow[l].d]!=1){
    v1[cow[l].d]--;
    ++l;
}//缩减左边界
while (v1[cow[r].d]!=1){
    v1[cow[r].d]--;
    --r;
}//缩减右边界
LL fir=cow[r].x-cow[l].x;//得到第一个答案
l=1;
r=n;
while (v2[cow[r].d]!=1){
    v2[cow[r].d]--;
    --r;
}//缩减右边界
while (v2[cow[l].l]!=1){
    v2[cow[l].d]--;
    ++l;
}//缩减左边界
LL sec=cow[r].x-cow[l].x;//得到第二个答案
printf("%lld",min(fir,sec));

Code:

#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL n, l, r, fir, sec;
struct node{
    LL x, d;
} cow[60005];
bool cmp(node a, node b){
    return a.x < b.x;
}
map<LL, LL> v1,v2;
int main(){
    scanf("%lld", &n);
    for (LL i = 1; i <= n; i++){
        scanf("%lld%lld", &cow[i].x, &cow[i].d);
        v1[cow[i].d]++;
        v2[cow[i].d]++;
    }
    sort(cow + 1, cow + 1 + n, cmp);
    l=1,r=n;
    while (v1[cow[r].d] != 1){
        v1[cow[r].d] -= 1;
        r--;
    }
    while (v1[cow[l].d] != 1){
        v1[cow[l].d] -= 1;
        l++;
    }
    fir = cow[r].x - cow[l].x;
    l = 1, r = n;
    while (v2[cow[l].d] != 1){
        v2[cow[l].d]--;
        l++;
    }
    while (v2[cow[r].d] != 1){
        v2[cow[r].d]--;
        r--;
    }
    sec = cow[r].x - cow[l].x;
    printf("%lld", min(fir, sec));
    return 0;
}