题解 P1311 【选择客栈】

晚安晚安 · 2018-11-02 23:48:59 · 题解

欢迎大家来到本蒟蒻的第二篇题解（希望能过管理员qwq）。

前言 不知道还有没有开的像我这么小的，只有2个数组，加起来就100多，而且代码挺短，和大家分享下我的想法：

我的做法:模拟之后,直接一路递推

change[i]存的是i色调客栈距离前一个能够满足p要求的客栈中间隔了多少个待机（也就是不满足要求）的客栈

而sum[i]存的是i色调客栈之前的客栈能够满足要求的客栈总数，（具体做法是和DRJ大佬出校门的时候想到的）

边输入边处理，当到i的时候，如果i之前有个客栈的消费满足小于p，那么这个客栈之前的所有客栈都可以和这个i进行一次匹配，而怎么得到之前满足的数目呢，这时候就要看看i本身怎么处理。

1.如果i本身满足要求小于p，那么就说明i之前的所有待机的客栈在接下来的i-n客栈中都可以匹配一次，所以一次for循环，把change[j]加到sum[j]中去，接下来ans再加一次sum[color]全部匹配一次。

2.如果i本身不满足的话，那么同样要进行一次ans+sum[color]，原因的话看懂了1就明白了。它不满足，如果接下来的i+1-n客栈中没有一个消费满足小于p的消费，那么是不是说明现在的这个i客栈对接下来的客栈一点贡献都没有了？所以把它放到change数组，change[color]++，如果接下来能够碰上为它搭桥（就是满足最低消费小于p）的客栈就把它放到sum，让它能够对接下来的客栈ans做贡献。

最后直接输出ans，愉快的AC

QVQ

上菜：

#include<cstdio>
using namespace std;
int change[55], sum[55], ans, n, k, p;
int main()
{
    scanf("%d%d%d", &n, &k, &p);
    for(int i = 1; i <= n; ++i){
        int color, cos;
        scanf("%d%d", &color, &cos);
        if(cos <= p){
            for(int j = 0; j <= 50; ++j)
                if(change[j]){sum[j]+=change[j];change[j] = 0;}
            ans += sum[color];
            ++sum[color];
        }
        else
        ++change[color], ans += sum[color];
    }
    printf("%d", ans);
    return 0;
}