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() {
    int actions[MAX_N];
    int n = 0;
    char line[10000];
    
    // 读取输入
    if (fgets(line, sizeof(line), stdin)) {
        char* token = strtok(line, " ");
        while (token != NULL && n < MAX_N) {
            actions[n++] = atoi(token);
            token = strtok(NULL, " ");
        }
    }

    // 计算并输出最大得分
    printf("%d\n", calculate_max_score(actions, n));

    return 0;
}

• Javascript

function calculateMaxScore(actions) {
    const totalActions = actions.length;
    
    // 初始化三个数组，用于记录不同类型的得分
    const positiveScores = new Array(totalActions).fill(0);  // 正向得分数组
    const penaltyScores = new Array(totalActions).fill(0);   // 累计延迟得分数组
    const finalScores = new Array(totalActions).fill(0);     // 最终得分数组

    // 初始化第一个时间点的得分
    positiveScores[0] = actions[0];
    finalScores[0] = actions[0];

    // 遍历每个时间点，计算得分
    for (let time = 1; time < totalActions; time++) {
        // 计算正向得分，但不超过100
        positiveScores[time] = Math.min(100, positiveScores[time - 1] + actions[time]);
        
        // 计算累计延迟得分
        penaltyScores[time] = penaltyScores[time - 1] + positiveScores[time - 1];
        
        // 计算最终得分
        finalScores[time] = positiveScores[time] - penaltyScores[time];

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

    // 返回最大得分
    return Math.max(...finalScores);
}

// 读取输入并处理
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.question('', (input) => {
    const actions = input.split(' ').map(Number);
    console.log(calculateMaxScore(actions));
    rl.close();
});

• Java

import java.util.Scanner;

public class Main {
    public static int calculateMaxScore(int[] actions) {
        int totalActions = actions.length;
        
        // 初始化三个数组，用于记录不同类型的得分
        int[] positiveScores = new int[totalActions];  // 正向得分数组
        int[] penaltyScores = new int[totalActions];   // 累计延迟得分数组
        int[] finalScores = new int[totalActions];     // 最终得分数组

        // 初始化第一个时间点的得分
        positiveScores[0] = actions[0];
        finalScores[0] = actions[0];

        int maxScore = finalScores[0];

        // 遍历每个时间点，计算得分
        for (int time = 1; time < totalActions; time++) {
            // 计算正向得分，但不超过100
            positiveScores[time] = Math.min(100, positiveScores[time - 1] + actions[time]);
            
            // 计算累计延迟得分
            penaltyScores[time] = penaltyScores[time - 1] + positiveScores[time - 1];
            
            // 计算最终得分
            finalScores[time] = positiveScores[time] - penaltyScores[time];

            // 更新最大得分
            maxScore = Math.max(maxScore, finalScores[time]);

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

        return maxScore;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(" ");
        int[] actions = new int[input.length];
        
        for (int i = 0; i < input.length; i++) {
            actions[i] = Integer.parseInt(input[i]);
        }

        System.out.println(calculateMaxScore(actions));
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <string>

using namespace std;

int calculate_max_score(const vector<int>& actions) {
    int total_actions = actions.size();
    
    // 初始化三个数组，用于记录不同类型的得分
    vector<int> positive_scores(total_actions, 0);  // 正向得分数组
    vector<int> penalty_scores(total_actions, 0);   // 累计延迟得分数组
    vector<int> final_scores(total_actions, 0);     // 最终得分数组

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

    // 遍历每个时间点，计算得分
    for (int time = 1; time < total_actions; ++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];

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

    // 返回最大得分
    return *max_element(final_scores.begin(), final_scores.end());
}

int main() {
    string line;
    getline(cin, line);
    istringstream iss(line);
    vector<int> actions;
    int num;
    while (iss >> num) {
        actions.push_back(num);
    }

    cout << calculate_max_score(actions) << endl;
    return 0;
}