华为OD机试-日志采集 E100

题目描述

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

如果上报太频繁，会对服务端造成压力;

如果上报太晚，会降低用户的体验;

如果一次上报的条数太多，会导致超时失败。

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

1. 每成功上报一条日志，奖励1分

2. 每条日志每延迟上报1秒，扣1分

3. 积累日志达到100条，必须立即上报

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

输入描述

按时序产生的日志条数 $T1,T\mathrm{2...}Tn$，其中

• $1\le n\le 1000$

• $0\le Ti\le 100$

输出描述

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

示例1

输入

1 98 1

输出

98

说明

T1 时刻上报得1分

T2 时刻上报得98分，最大

T3 时刻上报得 0分

示例2

输入

50 60 1

输出

50

说明

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

示例3

输入

3 7 40 10 60

输出

37

说明

T1时刻上报得3分

T2时刻上报得7分

T3时刻上报得37分，最大

T4时刻上报得-3分

T5时刻上报，因为已经超了100条限制，所以只能上报100条，得-23分

题解

根据题意，只有本次上报时间内产生的数据是可以得分的项目
$f(n)=\{\begin{array}{ll}array[n]& 类加和\le 100\\ array[n]-preSum& 累加和\ge 100\end{array}$

前一秒的上报不得分,再向前的记录会扣分，

扣分值为 :

$f(n)=\{\begin{array}{ll}array[n]& n<2\\ {\sum }_{i=0}^{n-2}array[i]\ast (n-i-1)& n\ge 2\end{array}$

源码 Java

public class LogUpload {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String[] split = scanner.nextLine().split(" ");

		int[] arr = new int[split.length];

		int max = 0;
		int sum = 0;
		for (int i = 0; i < split.length && sum < 100; i++) {
			arr[i] = Integer.parseInt(split[i]);
			int subTotal = 0;
			// 计算该次上报可以得分的部分
			int next = arr[i];
			if (sum + arr[i] > 100) {
				next = 100 - sum;
			}
			sum += arr[i];
			// 计算该次上报扣分的部分
			for (int ii = 0; ii < i - 1; ii++) {
				subTotal += arr[ii] * ( i - ii - 1);
			}
			// 比较是否取得最大值
			max = Math.max(max, next - subTotal);
		}
		System.out.println(max);
	}
}