蓝桥杯2025年第十六届省赛真题-研发资源分配

在蓝桥科技公司，A 部门和 B 部门正在竞争一种新型 AI 芯片的研发资源。 为了公平分配资源，公司设计了一个为期 N 天的分配方案： 

每天早上，A 部门和 B 部门各自提交一个需求等级（从 1 到 N 的整数）。 

提交等级较高的部门获得当天的资源，资源份额等于当天的日期编号（第 1 天为 1 单位，第 2 天为 2 单位，依次递增）。若两部门提交的等级相同，则当 天资源作废，双方均无法获得资源。 

每个部门必须在 N 天内使用 1 到 N 的所有等级，且每个等级只能使用一 次。 

有趣的是，A 部门在 B 部门内部安插了一名 “间谍”，提前获知了 B 部门的 需求等级提交顺序，记为排列 (P₁, P₂, . . . , P_N)，其中 Pi 表示 B 部门在第 i 天提 交的需求等级。 

现在，请你帮助 A 部门分析，在已知 B 部门需求等级顺序的情况下，A 部 门的总资源份额减去 B 部门的总资源份额的差值最大可以是多少？

第一行包含一个整数 N，表示分配方案的天数。 

第二行包含 N 个整数 P₁, P₂, . . . , P_N，表示 B 部门在第 1 天到第 N 天提交 的需求等级。

输出一个整数，表示 A 部门的总资源份额减去 B 部门的总资源份额的最大 差值。

3
1 3 2

2

【样例说明】 

A 部门可以选择排列 [2, 1, 3]： 

第 1 天：A(= 2) > B(= 1)，A 获得 1 单位资源； 

第 2 天：A(= 1) < B(= 3)，B 获得 2 单位资源； 

第 3 天：A(= 3) > B(= 2)，A 获得 3 单位资源。

两者的差值为 4 − 2 = 2。 

【评测用例规模与约定】 

对于 20% 的评测用例，1 ≤ N ≤ 11，1 ≤ P_i ≤ N，P₁, P₂, . . . , P_N 各不相同。 

对于 100% 的评测用例，1 ≤ N ≤ 10⁵，1 ≤ P_i ≤ N，P₁, P₂, . . . , P_N 各不相 同。