题解：CF1687A The Enchanted Forest
一开始以为是一个 $\texttt{dp}$，仔细一看发现只是一个普通的贪心。
若 $k \le n$，则不能收集完或恰好收集完所有的蘑菇。如果一个地方的蘑菇被重复地收取，则会浪费之前到达该地所花的时间。我们的目标是使得时间之和最大，故一个地方重复遍历不可取。尝试模拟后可以发现，对于新长出来的蘑菇，收集的数目是确定的，为 $\sum_{i = 1}^{k - 1}$，运用高斯求和公式后得到 $\dfrac{k \times (k - 1)}{2}$。现在问题就转换为求原有蘑菇序列的长度为 $k$ 的区间和的最大值，因此只需要类似滑动窗口般的思想扫一遍求出最大值。
若 $k > n$，则可以收集完原有的所有的蘑菇（由于每次只长一个蘑菇，初始位置的蘑菇数量大于等于 $1$，所以收集原有的所有蘑菇至少不比不全收劣），对于如何求出新长出的蘑菇的最值的序列的问题，我的方法是逆向考虑。由于收集完原有的所有的蘑菇，所以每个节点至少到一次，令最后一次所到达的节点为 $n$，倒数第二个到达的点为 $n - 1$，以此类推……那么可以发现，$n$ 点最后生长的一个蘑菇没用能够采集，$n - 1$ 点有两个，一次类推……所以说，在 $k$ 秒后，共新长出了 $n \times k$ 个蘑菇，而节点 $n$ 至 $1$ 分别有 $1,2,\cdots,n$ 个蘑菇未采集，即总共采集到的新长出的蘑菇数量为 $n \times k - \sum_{i = 1}^{n} = n \times t - \frac{(n + 1) \times n}{2}$。
时间复杂度为 $O(n)$，可以通过本题。最后，千千万万注意开 $\texttt{long long}$。代码如下：
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 2e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int t;
ll k,n,ans,a[MAX];
int main ()
{
t = read ();
while (t--)
{
ans = 0;
n = read ();k = read ();
for (int i = 1;i <= n;++i) a[i] = read ();
if (k <= n)
{
ll s = 0;
for (int i = 1;i <= n;++i)
{
if (i <= k) s += a[i],ans = s;
else ans = max (ans,s - a[i - k] + a[i]),s = s - a[i - k] + a[i];
}
ans += k * (k - 1) >> 1;
}
else
{
for (int i = 1;i <= n;++i) ans += a[i];
ans += n * k;
ans -= n * (n + 1) >> 1;
}
printf ("%lld\n",ans);
}
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
