题解 P1311 选择客栈

哦哟筷子 · 2019-10-01 14:06:21 · 题解

这道体原来是校内模拟赛的时候做的，一开始确实没什么思路，只想到 O(n^2) 的暴力。突破口是在想到一个结论：

如果两个点i,j满足条件（即颜色相同，且中间有一个客栈消费小于等于P）,距离为d，那么与端点颜色相同且与其中任何一个距离大于d且颜色相同的点都满足条件。

举个例子（有、、丑）

但是这样似乎会有重复的问题，而且复杂度还是没有优化。考虑如果能一遍扫完，观察数据，发现颜色种类k \le 50可以运用类似前缀和的思想，求出每一种颜色的前缀和，费用过高的可以直接读入数据的时候判定掉，并用一个指针nxt_i，指向上一个距离该点最近且满足条件的位置。

需要注意当这个点的nxt指向本身的时候，要把这个点排除掉，因为两人不能住在同一个客栈

代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2E5 + 10;
int N,K,P;
int a[MAXN],b;
int clr[MAXN][60],nxt[MAXN];
long long ans = 0;
int main() {
    scanf("%d%d%d",&N,&K,&P);
    for (register int i = 1; i <= N; i++) {
        scanf("%d%d",&a[i],&b);
        for (register int j = 0; j < K; j++) {
            clr[i][j] = clr[i - 1][j]; //每种颜色的前缀和
        }
        clr[i][a[i]]++;
        if (b <= P) { //指针，指向上一个满足条件的点
            nxt[i] = i;
        }
        else {
            nxt[i] = nxt[i - 1];
        }
    }
    for (register int i = 1; i <= N; i++) {
        if (nxt[i] == i) {
            ans += clr[i - 1][a[i]];
        }
        else {
            ans += clr[nxt[i]][a[i]];
        }
    }
    printf("%lld",ans);
    return 0;
}

完结撒花qwq