目录

题目描述

输入描述

输出描述

用例

题目解析

算法源码

题目描述

日志采集是运维系统的的核心组件。日志是按行生成，每行记做一条，由采集系统分批上报。

• 如果上报太频繁，会对服务端造成压力;
• 如果上报太晚，会降低用户的体验；
• 如果一次上报的条数太多，会导致超时失败。

为此，项目组设计了如下的上报策略：

1. 每成功上报一条日志，奖励1分
2. 每条日志每延迟上报1秒，扣1分
3. 积累日志达到100条，必须立即上报

给出日志序列，根据该规则，计算首次上报能获得的最多积分数。

输入描述

按时序产生的日志条数 T1,T2…Tn，其中 1<=n<=1000，0<=Ti<=100

输出描述

首次上报最多能获得的积分数

用例

题目解析

用例意思是：

如果在T1时刻上报日志，由于只有1条日志，因此可得1分。

如果在T2时刻上报日志，由于T1时刻产生的1条日志延迟了1秒上报，因此要扣1分，到了T2时刻可以上报1+98条日志，可得99分，因此99-1=98分。

如果在T3时刻上报日志，则T1日志延迟了2s，要扣1*2分，T2日志延迟了1s，要扣98*1分，T3时刻可以上报100条日志，可得100分，因此100-2-98=0分。

我的解题思路如下：

这种前后数据具有依赖关系，一般都是用动态规划DP解决。

首先，我用前缀和思路，将每个时刻，可得的正向分计算出来缓存进dp数组中。所谓正向分，比如T2时刻积累了99条日志，那么就应该得到99分。这是正向得分。但是最终得分还需要扣除延迟上报的负向得分。比如T2时刻上报日志的话，则T1时刻产生的每条日志都需要扣除1分，这是负向得分。因此T2时刻的最终得分是：正向得分  - 负向得分 = 99 - 1 = 98分。

计算正向得分时的dp公式为：

dp[0] = arr[0]

dp[i] = arr[i] + dp[i-1]

但是题目中说了，如果积累到100条日志，则必须在那个时刻将所有日志上报，因此dp公式需要修改为：

dp[0] = arr[0]

dp[i] = arr[i] + (dp[i-1] >= 100 ? 0 : dp[i-1])

负向得分的计算：

如果在T1时刻上报的话，无负向得分，即delay[0] = 0

如果在T2时刻上报的话，则负向得分来自于T1时刻， 即 deylay[1] = delay[0] + dp[0] = 0 + 1

如果在T3时刻上报的话，则负向得分来自于T1时刻， 即 deylay[2] = delay[1] + dp[1] = 1 + 99

因此可得 delay[i] = delay[i-1] + dp[i-1]

但是由于当日志满100条时，就必须上报，因此delay应该清零。

即 delay[i] = dp[i-1] >= 100 ? 0 : delay[i-1] + dp[i-1]

算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});rl.on("line", (line) => {const arr = line.split(" ").map(Number);const dp = [arr[0]]; // dp[i]表示：第i时刻可得的正向分const delay = [0]; // delay[i]表示：第i时刻被扣除的负向分const score = [arr[0]]; // score[i]表示：第i时刻最终得分for (let i = 1; i < arr.length; i++) {if (dp[i - 1] < 100) {dp[i] = arr[i] + dp[i - 1];delay[i] = delay[i - 1] + dp[i - 1];} else {dp[i] = arr[i];delay[i] = 0;}score[i] = dp[i] - delay[i];}console.log(Math.max.apply(null, score));
});