华为机试 - 日志首次上报最多积分
admin
2024-03-28 08:38:55
0次

目录

题目描述

输入描述

输出描述

用例

题目解析

算法源码


题目描述

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

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

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

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

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

输入描述

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

输出描述

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

用例

输入

1 98 1

输出98
说明T1 时刻上报得 1 分
T2 时刻上报得98分,最大
T3 时刻上报得 0 分

题目解析

用例意思是:

如果在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));
});

相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...