P10229 题解

· · 题解

题目分析

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;
}