Educational Codeforces Round 96 (Rated for Div. 2) 解题报告

CF1430F Realistic Gameplay

Educational Codeforces Round 96 第六题,贪心题。

题目链接

题意翻译

有 \( n \) 波怪物,你有一把枪,枪的弹夹量为 \(k\),第 \( i \) 波怪物数量为 \( a _ i \),在第 \( l _ i \) 到 \( r _ i \) 时间出现(\( r _ i \leq l _ { i + 1 } \)),你可以在任意时刻打出一发子弹击杀一只怪物且不耗费时间,你必须在 \( \left[ l _ i , r _ i \right] \) 时间内消灭 \( a _ i \) 只怪物,你每次换弹都需要将弹夹(包括里面的子弹)扔掉,在尽量保证通关的情况下,需要的最多的子弹数为多少。

题解

我们只要考虑换弹夹所带来的额外消耗就够了。尽量不换是最优的。考虑什么时候必须换弹夹。

需不需要换弹夹由后面决定。因为后面如果特别紧,这个时候就必须换。如果后面不是那么紧张,就可以打完子弹再换。

受这种启发,考虑尽量靠后地射击。如果这一波人数特别多,但是上一波也挺多的,并且 \( r _ { i – 1 } = l _ i \),如果我们安排了过多在 \( l _ i \) 时间射击,就可能导致前一段无法消灭敌人。所以尽可能安排在 \( \left( l _ i , r _ i \right] \) 去射击。

设 \( f _ i \) 表示第 \( i \) 波敌人来时的必要射击次数。
如果 \( i \) 段和 \( i + 1 \) 段重叠,那么在 \( i \) 的时间段内要多设 \( f _ { i + 1 } \) 个。

从后往前递推即可,时间复杂度为 \( \Theta ( n ) \)。

#include <bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
static char buf[100000], *p1 = buf, *p2 = buf;
inline int read(void)
{
    reg char ch = getchar();
    reg int res = 0;
    while (ch < '0' || '9' < ch)
        ch = getchar();
    while ('0' <= ch && ch <= '9')
        res = 10 * res + ch - '0', ch = getchar();
    return res;
}

const int MAXN = 2e3 + 5;

int n, k;
int l[MAXN], r[MAXN], a[MAXN];
int dp[MAXN];

int main()
{
    n = read(), k = read(); //读入数据
    for (reg int i = 1; i <= n; ++i)
        l[i] = read(), r[i] = read(), a[i] = read(); //读入数据
    for (reg int i = n; i >= 1; --i)
    {
        reg int tmp = a[i];
        if (r[i] == l[i + 1] && i != n)
            tmp += dp[i + 1]; //区间重叠
        if (tmp > 1ll * (r[i] - l[i] + 1) * k)
        { //不可能打完所有怪物
            puts("-1");
            return 0;
        }
        dp[i] = max(0ll, tmp - 1ll * (r[i] - l[i]) * k); //转移
    }
    reg int sum = k;
    reg ll ans = 0;
    for (reg int i = 1; i <= n; ++i)
    {
        if (sum < dp[i])
        { //换弹夹
            ans += sum;
            sum = k;
        }
        ans += a[i];                    //还能用
        sum = (sum - a[i] % k + k) % k; //用掉 a[i] 子弹
    }
    printf("%lld\n", ans); //输出答案
    return 0;
}
Pages: 1 2 3 4 5 6 7 8 9