题解 P4266 【[USACO18FEB]Rest Stops】

木木！ · 2019-08-14 15:18:11 · 题解

这题可以用每次暴力比较贪心的做法。如果数据随机，这种做法的时间复杂度为\Theta(n\log n)。但是如果数据构造了的话，这种做法可以被卡到\Theta(n^2)。排序的做法是\Theta(n\log n)，这里介绍一种\Theta(n)的单调队列做法。

单调队列模板题

可以发现，每次如果一个休息站的位置比较远且c_i比较大的话，就可以把前面那个挤出去。这样就很容易想到结合单调队列的贪心。

由于输入数据已经按照位置排好序，所以只需要\Theta(n)单调队列，然后\Theta(n)扫一遍单调队列就好。

三个int乘起来可能会爆int，要记得开long long。因为都是10^6级别，不会爆long long。

附AC代码：

#include <cstdio>
using namespace std;

int q[100005];
int xi[100005];
int ci[100005];

int main()
{
    int l,n,f,b;
    scanf("%d%d%d%d",&l,&n,&f,&b);
    for(int i=1; i<=n; ++i)
    {
        scanf("%d%d",xi+i,ci+i);
    }

    int head = 0;
    for(int i=1; i<=n; ++i)
    {
        while(head && ci[i]>=ci[q[head]])
        {
            --head;
        }
        ++head;
        q[head] = i;
    }

    long long ans = 0;
    for(int i=1; i<=head; ++i)
    {
        ans += 1LL*(xi[q[i]]-xi[q[i-1]])*(f-b)*ci[q[i]];
    }

    printf("%lld",ans);
}