P12161 [蓝桥杯 2025 省 Java B] 研发资源分配

题目描述

在蓝桥科技公司，$A$ 部门和 $B$ 部门正在竞争一种新型 AI 芯片的研发资源。

为了公平分配资源，公司设计了一个为期 $N$ 天的分配方案：

每天早上，$A$ 部门和 $B$ 部门各自提交一个需求等级（从 $1$ 到 $N$ 的整数）。提交等级较高的部门获得当天的资源，资源份额等于当天的日期编号（第 $1$ 天为 $1$ 单位，第 $2$ 天为 $2$ 单位，依次递增）。若两部门提交的等级相同，则当天资源作废，双方均无法获得资源。

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

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

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

输入格式

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

第二行包含 $N$ 个整数 $P_1,P_2,\dots ,P_N$，表示 $B$ 部门在第 $1$ 天到第 $N$ 天提交的需求等级。

输出格式

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

输入输出样例 #1

输入 #1

3
1 3 2

输出 #1

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\le N\le 11$，$1\le P_i\le N$，$P_1,P_2,\dots ,P_N$ 各不相同。
• 对于 $100\%$ 的评测用例，$1\le N\le 10^5$，$1\le P_i\le N$，$P_1,P_2,\dots ,P_N$ 各不相同。

C++实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N = 1e5 + 10;

struct node{
	int val, pos;
}a[N];

bool cmp(node x, node y)
{
	return x.val > y.val;
}
ll n;
ll sum; 
ll ans;

int main()
{
	cin >> n;
	sum = (1 + n) * n / 2; // 总得分
	for (int i = 1; i <= n; i++) {
		cin >> a[i].val;
		a[i].pos = i;
	}
	sort(a + 1, a + 1 + n, cmp);
	for (int i = 1; i <= n; i++) {
		sum -= a[i].pos; 
		ans = max(ans, sum - a[i].pos);
	}
	cout << ans;
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容