买咖啡

Posted on Edited on In

题目大意：咖啡它的价格每小时都会发生变化。现在，考虑长为 n时的一段时间，在第i时中，咖啡的价格为\(c_i\)，由于秋冬季容易感冒， KSkun 不会喝冷了的咖啡，1杯咖啡在经过 h时后会冷，这之后 KSkun 不会再喝它了。1杯咖啡可以让 KSkun 保持清醒 1时，他想知道在每个小时中分别买几杯咖啡，才能在花费最少的情况下在每个小时中都能够通过喝 杯热的咖啡保持清醒。 在本题中，你只需要输出第 这些小时中的答案即可。在花费最少的情况下喝到最新鲜的咖啡（即如果有相同价格的咖啡能选择，选择时间最后的）。

转化题意，也就是说，从当前这个物品的前h个里面选一个最小的买了，用单调队列来转移

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
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 66;

int n, h, b, e;
int c[N], q[N], res[N];

signed main()
{
    int i, j, k;
    while (scanf ("%lld%lld%lld%lld", &n, &h, &b, &e) != EOF)
    {
        for (i = 1; i <= n; ++ i) c[i] = read();
        memset(q, 0, sizeof q), memset(res, 0, sizeof res);
        int l = 1, r = 0;
        for (i = 1; i <= n; ++ i)
        {
            while (l <= r && q[l] + h <= i) ++ l;
            while (l <= r && c[q[r]] >= c[i]) -- r;
            q[++ r] = i;
            ++ res[q[l]];
        }
        for (i = b; i <= e; ++ i) put(res[i]);
        puts("");
    }
    return 0;
}

总结：

期望得分：100+？+50pts

实际得分：100+0+50pts

第二题自己在一个错误的方向上走了很远，应该多换方向考虑，自己的做题思路太容易僵化