bzoj 5438: 青蛙

题意：

有$n$块石头排成一行，从左到右依次编号为$1$到$n$，相邻两块石头之间的距离为$1$。有$m$只青蛙，开始时都位于$1$号石头，它们都需要跳到$n$号石头上。青蛙只能跳到更靠右的石头上。如果第$i$只青蛙的某次跳跃的距离超过$d$，那么需要付出$c_i$的代价。求出满足以下两个条件时，总代价的最小值：
(1) 石头$a_1,a_2,a_3,…,a_k$必须被跳到恰好一次。
(2) 其它石头(不包含$1$号石头和$n$号石头)不能被跳到。
有多组数据。

题解：

首先，石头肯定越多越好，因为这样石头密度大一点，需要花费的概率就小一点。所以如果有青蛙在中途需要花费，不如让他花费一次的代价直接跳到$n$，还可以腾出更多的石头。青蛙跳有个贪心的策略，就是每次让当前最后那只青蛙跳到最前面的石头上。这样要花费的概率最小。而我们前面说要花费的一步要跳完，所以只有免费的青蛙在石头中间跳。同时这个还可以保证所有免费青蛙的位置都是连续的。免费青蛙的个数就是间隔为$d$的最小的石头数。扫一遍求出来就好了。最后把最大的那些价格分给免费青蛙，剩下的加起来就好了。

代码：

#include <bits/stdc++.h>
using namespace std;

int T, n, m, k, d, c[100010], a[100010];

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d%d%d", &n, &m, &k, &d);
        for (int i = 1; i <= m; i++) scanf("%d", &c[i]);
        for (int i = 1; i <= k; i++) scanf("%d", &a[i]);
        if (d >= n - 1)
        {
            puts("0");
            continue;
        }
        a[0] = 1;
        a[k + 1] = n;
        sort(a + 1, a + 1 + k);/*
        for (int i = 0; i <= k + 1; i++) printf("%d ", a[i]);
        puts("");*/
        int hh = m;
        for (int l = 0, r = 1; l <= k; l++)
        {
            while (r <= k && a[r + 1] - a[l] <= d) r++;
            hh = min(hh, r - l);
            if (r == k + 1) break;
        }
        // printf("%d\n", hh);
        if (hh == 0) // 必须花钱
        {
            int mn = 2147483647;
            long long ans = 0;
            for (int i = 1; i <= m; i++) mn = min(mn, c[i]), ans += c[i];
            ans -= mn;
            for (int i = 0; i <= k; i++)
                if (a[i + 1] - a[i] > d) ans += mn;
            printf("%lld\n", ans);
        }
        else
        {
            long long ans = 0;
            sort(c + 1, c + 1 + m);
            for (int i = 1; i <= m - hh; i++)
                ans += c[i];
            printf("%lld\n", ans);
        }
    }
}