P3029. Cow Lineup S

发表于 分类于 阅读次数： Waline： 本文字数： 149 阅读时长 ≈ 1 分钟

考点

  • 双指针

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 50;
int n, cnt;
unordered_map<int, int> mp;

struct node {
  int x_, id_;
  bool operator<(node &x) { return x_ < x.x_; }
} arr[maxn];

int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> arr[i].x_ >> arr[i].id_;
    ++mp[arr[i].id_];
  }
  sort(arr + 1, arr + 1 + n);
  cnt = mp.size(), mp.clear();
  int head = 1, tail = 1, ans = INT_MAX;
  while (head <= tail && tail <= n) {
    ++mp[arr[tail].id_];
    while (head <= tail && mp.size() == cnt) {
      ans = min(ans, arr[tail].x_ - arr[head].x_);
      if (--mp[arr[head].id_] == 0) mp.erase(arr[head].id_);
      ++head;
    }
    ++tail;
  }
  cout << ans;
  return 0;
}

思路

根据x排序后，用双指针+哈希表维护当前区间内的奶牛种类数即可。