自动搬运

查看原文

来自洛谷，原作者为

	yitian_ 高估 T3 以至于打个深搜就睡觉去了/kel

搬运于2025-08-24 22:55:58，当前版本为作者最后更新于2024-05-14 22:46:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目分析

Marko 购买了一系列书籍，每本书都有一个吸引力值。他有限的时间内（$t$ 分钟），想要获得尽可能多的灵感值。他可以选择完整阅读一本书，也可以只通过阅读封面了解其内容。

问题可以转化为如何选择阅读哪些书籍，以使得最终灵感值最大。由于书籍的吸引力按照从左到右单调不减的方式排列，因此我们应该尽可能跳过吸引力较小的书籍，以便能够阅读到后面吸引力更大的书籍。

思路

我们可以使用前缀和来快速计算阅读一段连续的书籍的吸引力之和。定义一个数组 $p$，其中 $p_i$ 表示前 $i$ 本书籍的吸引力之和。这样，阅读从第 $i$ 本书到第 $j$ 本书的吸引力之和可以表示为 $p_j - p_{i-1}$。

接着采用贪心的思想来解决这个问题。具体步骤如下：

1. 从 $i=0$ 开始遍历，表示跳过 $i$ 本书。
2. 计算在跳过 $i$ 本书后，还能阅读多少本书，设为 $s$。
3. 计算在跳过 $i$ 本书后，最后一本能读的书的编号，设为 $l$。
4. 根据前缀和数组计算阅读这些书籍的吸引力之和，即 $p_l - p_i$。
5. 更新 $ans$，即取当前计算得到的吸引力之和与 $ans$ 中的较大者。

最后得出的 $ans$ 即为最大灵感值。

C++ 代码实现

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

long long k[200010],p[200010]; // 定义吸引力数组和前缀和数组

int main() 
{
    long long n,t,a,b,ans=0; // 定义书的数量，阅读时间，完整阅读时间，阅读封面时间和最终结果
    cin >> n >> t >> a >> b; // 输入书的数量，阅读时间，完整阅读时间和阅读封面时间
    for(long long i=1;i<=n;i++) 
	{
        cin >> k[i]; // 输入每本书的吸引力值
    }
    for(long long i=1;i<=n;i++) 
	{
        p[i]=p[i-1]+k[i]; // 计算前缀和
    }
    for(long long i=0;i<=n;i++) 
	{
        if(i*b>t) break; // 如果跳过前面的书的时间大于 t，就退出循环
        long long s=(t-i*b)/a; // 计算跳过i之前的所有书，还能阅读的书的数量
        long long l=min(n,s+i); // 计算跳过i之前的所有书，还能阅读到的书的编号，有时可能会大于 n，所以和 n 取最小值
        ans=max(ans,p[l]-p[i]); // 更新最大灵感值
    }
    cout << ans << endl; 
    return 0;
}