P2564 [SCOI2009] 生日礼物

06-09-2021 约 480 字预计阅读 1 分钟

去洛谷上看了一眼算法标签噫！好！单调队列！然后就自行脑补了DP二字，然后就想不出来了……

结果发现这就是单调队列，莫得DP

思路：

既然要求的与距离有关，那就从距离下手，先定义个结构体把所有的点的位置和种类存起来，再从小到大排一下序，然后就可以开始计算了

首先从第1个点向第n个点枚举，开一个times数组来存当前遍历到第i个点，一种点的类型被访问到的次数。然后把现在的点怼到队列里，顺便把累计访问过的点的种类的总数统计一下。

当现在访问过的点的种类=k时就要开始从队列里（这个队列里点的位置是严格递增的）向外踢点了

1
2
3
4
5
6


while (typecnt == k) {
  ans = min(ans, pnt[tail].pos - pnt[head].pos); // update ans
  times[pnt[head].type]--;
  head++;
  if (times[pnt[head - 1].type] == 0) typecnt--;
}

FULL VERSION of CODE:

 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
33
34
35
36
37
38
39
40
41


#include <bits/stdc++.h>
using namespace std;
const int maxn = 1001;

struct PNT {
  int type, pos;
} pnt[maxn], que[maxn];
int n, k, sum = 1, typecnt = 0, ans = 0x3f3f3f3f;
int times[maxn];
bool cmp(PNT a, PNT b) { return a.pos < b.pos; }
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= k; i++) {
    int t;
    scanf("%d", &t);
    for (int j = 1; j <= t; j++) {
      int p;
      scanf("%d", &p);
      pnt[sum].pos = p;
      pnt[sum].type = i;
      sum++;
    }
  }
  sum--;
  sort(pnt + 1, pnt + 1 + sum, cmp);
  int head = 1, tail = 0;
  for (int i = 1; i <= sum; i++) {
    que[++tail] = pnt[i];
    times[pnt[i].type]++;
    if (times[pnt[i].type] == 1) typecnt++;
    while (typecnt == k) {
      ans = min(ans, pnt[tail].pos - pnt[head].pos);
      times[pnt[head].type]--;
      head++;
      if (times[pnt[head - 1].type] == 0) typecnt--;
    }
  }
  cout << ans << endl;
  return 0;
}

目录

P2564 [SCOI2009] 生日礼物

思路：