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

_Yuyuyu_ · 2025-11-30 18:02:10 · 题解

题解：P12161

25 分代码

看到这道题时第一个想到的是双指针。我们可以用两个指针记录当前 A 部门的最小和最大等级，如果当前 A 部门的最大等级大于 B 部门的当前等级，就用两等级相匹配，否则就用当前 A 部门的最小等级与 B 部门的当前等级相匹配。
代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,p[100005],tmp_a[100005],sum_a,sum_b;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>p[i];
    for(int i=1;i<=n;i++)tmp_a[i]=i;
    int l=1,r=n;
    for(int i=n;i>=1;i--){
        int t=p[i];
        if(tmp_a[r]>t)sum_a+=i,r--;
        else{
            if(t!=tmp_a[l])sum_b+=i;
            l++;
        }
    }
    cout<<sum_a-sum_b;
    return 0;
}

提交之后，等待 AC，却只有 25 分。
到底是哪里错了呢？原来如果当前 B 部门的等级很小的话，就不必用 A 部门当前最大的等级去和其匹配。
我们通过观察发现，可以先把 B 部门的所有等级按从大到小的顺序排序，然后枚举 A 部门与 B 部门碰掉多少个相同的等级能使两部门总资源份额的差值最大，最后就可以得出正确结果了。

AC 代码如下

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n,ans,sum;
struct node{
    int v,id;
}p[100005];
bool cmp(node a,node b){
    return a.v>b.v;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i].v;
        p[i].id=i;
    }
    ans=(n+n*n)/2;
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++){
        ans-=p[i].id;
        sum=max(sum,ans-p[i].id);
    }
    cout<<sum;
    return 0;
}

最后提醒大家：十年 OI 一场空，不开 ＿＿ 见祖宗。
蒟蒻刚写没几篇题解，各位巨佬多指教。