#PQJ1898x9686. QOJ 1898_9686

    ID: 2752 传统题 2000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTS 2025线段树

QOJ 1898_9686

第一试士兵(soldier) IOI2025 中国国家队选拔 士兵(soldier) 【题目描述】 有n 个士兵站成一排。初始时,编号为i 的士兵血量为ai。 你可以进行若干次(也可以不进行)进攻。每次进攻时,你可以选择一段区间 [l, r](1 ≤l ≤r ≤n),将编号在这一段区间内的士兵的血量减少1。每次进攻需要付 出m 的代价。 在所有的进攻结束后,若第i 个士兵的血量不超过0,那么你会获得bi 的收益。由 于士兵中敌友混杂,bi 有可能是负数。注意每个士兵的收益只会获得一次。 你需要找到一个进攻方案,来最大化收益总和减去代价总和。形式化地,设在你的 方案进攻了k 次,最终第i 个士兵的血量为ci,令pi 在ci ≤0 时为1 否则为0,则你 需要最大化(!n i=1 pi × bi) −m × k。最终,你需要给出收益总和减去代价总和的最大值 即可。 【输入格式】 从文件soldier.in 中读入数据。 .本.题.有.多.组.测.试.数.据。 输入的第一行包含一个正整数T 表示数据组数。 接下来依次输入每组测试数据,对于每组测试数据: 第一行包含两个整数n, m,分别表示士兵数量和单次进攻代价。 接下来n 行,每行包含两个整数ai, bi,分别描述每个士兵的血量和收益。 【输出格式】 输出到文件soldier.out 中。 对于每组数据输出一行包含一个整数,表示在所有可能的方案中可以得到的收益总 和减去代价总和的最大值。 【样例1 输入】 3 1 5 1 2 1 3 3 2 5 4 1 4 5 3 3 6 5 1 7 第8 页 共9 页 第一试士兵(soldier) IOI2025 中国国家队选拔 3 2 8 1 5 9 1 ‐100 10 1 5 11 3 2 12 1 5 13 1 ‐1 14 1 5 15 【样例1 输出】 12 1 6 2 7 3 【样例1 解释】 第一组测试数据中,一个最优方案为进攻三次,分别取区间[1, 5], [2, 4], [4, 4],最终 血量序列为(0, 0, −1, 0, 4),收益为b1 + b2 + b3 + b4 = 15,代价为3 × 1 = 3。可以证明 没有比该方案更优的方案,故输出15 −3 = 12。 第二组测试数据中,一个最优方案为进攻两次,分别取区间[1, 1], [3, 3]。 第三组测试数据中,一个最优方案为进攻一次,取区间[1, 3]。 【子任务】 设! n 表示单个测试点中所有测试数据的n 的和。对于所有测试数据,保证 • 1 ≤T ≤5 × 105, • 1 ≤n, ! n ≤5 × 105,1 ≤m ≤109, • ∀1 ≤i ≤n, 1 ≤ai ≤109, −109 ≤bi ≤109。 ! n ≤ 子任务编号 分值 特殊性质 5 × 105 ∀1 ≤i ≤n, bi ≥0 1 5 ∀1 ≤i ≤n, ai ≤5, 000 2 15 5, 000 3 20 105 4 无 2 × 105 5 25 5 × 105 6 15 第9 页 共9 页