E卷-日志采集系统(100分)
📝 日志采集系统
问题描述
日志采集是运维系统的核心组件。日志是按行生成,每行记做一条,由采集系统分批上报。
- 如果上报太频繁,会对服务端造成压力;
- 如果上报太晚,会降低用户的体验;
- 如果一次上报的条数太多,会导致超时失败。
为此,项目组设计了如下的上报策略:
- 每成功上报一条日志,奖励 1 分。
- 每条日志每延迟上报 1 秒,扣 1 分。
- 积累日志达到 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 分。
数据范围
题解
动态规划
这道题目要求我们计算日志上报系统能获得的最大积分。
关键在于理解积分规则和找出最佳上报时机。
解题思路如下:
- 遍历每个时间点,计算如果在该时间点上报能获得的积分。
- 维护三个数组:
positive_scores
:记录每个时间点累积的正向得分。penalty_scores
:记录每个时间点累积的延迟惩罚分。final_scores
:记录每个时间点的最终得分。
- 对于每个时间点,更新这三个数组:
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]
:计算最终得分。
- 如果累积日志数达到100,立即结束计算。
- 返回
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;
}
#OD##OD机考#OD刷题笔记 文章被收录于专栏
本专栏收集并整理了一些刷题笔记