E卷-日志采集系统(100分)

📝 日志采集系统

问题描述

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

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

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

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

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

输入格式

一行空格分隔的整数 ，表示按时序产生的日志条数，其中 ，。

输出格式

一个整数，表示首次上报最多能获得的积分数。

样例输入 1

1 98 1

样例输出 1

98

样例解释 1

时刻上报得 1 分， 时刻上报得 98 分（最大）， 时刻上报得 0 分。

样例输入 2

50 60 1

样例输出 2

50

样例解释 2

如果第 1 个时刻上报，获得积分 50。如果第 2 个时刻上报，最多上报 100 条，前 50 条延迟上报 1s，每条扣除 1 分，共获得积分为 100-50=50。

样例输入 3

3 7 40 10 60

样例输出 3

37

样例解释 3

时刻上报得 3 分， 时刻上报得 7 分， 时刻上报得 37 分（最大）， 时刻上报得 -3 分， 时刻上报，因为已经超了 100 条限制，所以只能上报 100 条，得 -23 分。

数据范围

题解

动态规划

这道题目要求我们计算日志上报系统能获得的最大积分。

关键在于理解积分规则和找出最佳上报时机。

解题思路如下：

1. 遍历每个时间点，计算如果在该时间点上报能获得的积分。
2. 维护三个数组：
   • positive_scores：记录每个时间点累积的正向得分。
   • penalty_scores：记录每个时间点累积的延迟惩罚分。
   • final_scores：记录每个时间点的最终得分。
3. 对于每个时间点，更新这三个数组：
   • positive_scores[i] = min(100, positive_scores[i-1] + actions[i])：累加日志数，但不超过100。
   • penalty_scores[i] = penalty_scores[i-1] + positive_scores[i-1]：计算延迟惩罚。
   • final_scores[i] = positive_scores[i] - penalty_scores[i]：计算最终得分。
4. 如果累积日志数达到100，立即结束计算。
5. 返回 final_scores 中的最大值。

参考代码

• Python

def calculate_max_score(actions):
    total_actions = len(actions)
    
    # 初始化三个数组，用于记录不同类型的得分
    positive_scores = [0] * total_actions  # 正向得分数组
    penalty_scores = [0] * total_actions   # 累计延迟得分数组
    final_scores = [0] * total_actions     # 最终得分数组

    # 初始化第一个时间点的得分
    positive_scores[0] = actions[0]
    final_scores[0] = actions[0]

    # 遍历每个时间点，计算得分
    for time in range(1, total_actions):
        # 计算正向得分，但不超过100
        positive_scores[time] = min(100, positive_scores[time - 1] + actions[time])
        
        # 计算累计延迟得分
        penalty_scores[time] = penalty_scores[time - 1] + positive_scores[time - 1]
        
        # 计算最终得分
        final_scores[time] = positive_scores[time] - penalty_scores[time]

        # 如果累积日志数达到100，立即结束循环
        if positive_scores[time] >= 100:
            break

    # 返回最大得分
    return max(final_scores)

# 主函数
if __name__ == "__main__":
    # 从输入获取日志序列
    actions = list(map(int, input().split()))
    # 计算并输出最大得分
    print(calculate_max_score(actions))

• C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 1000
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int calculate_max_score(int actions[], int n) {
    int positive_scores[MAX_N] = {0};  // 正向得分数组
    int penalty_scores[MAX_N] = {0};   // 累计延迟得分数组
    int final_scores[MAX_N] = {0};     // 最终得分数组
    int max_score = 0;

    // 初始化第一个时间点的得分
    positive_scores[0] = actions[0];
    final_scores[0] = actions[0];
    max_score = actions[0];

    // 遍历每个时间点，计算得分
    for (int time = 1; time < n; time++) {
        // 计算正向得分，但不超过100
        positive_scores[time] = MIN(100, positive_scores[time - 1] + actions[time]);
        
        // 计算累计延迟得分
        penalty_scores[time] = penalty_scores[time - 1] + positive_scores[time - 1];
        
        // 计算最终得分
        final_scores[time] = positive_scores[time] - penalty_scores[time];
        
        // 更新最大得分
        max_score = MAX(max_score, final_scores[time]);

        // 如果累积日志数达到100，立即结束循环
        if (positive_scores[time] >= 100) {
            break;
        }
    }

    return max_score;
}

int main() {