题解：P12149 【MX-X11-T3】「蓬莱人形 Round 1」科学

· · 题解

【MX-X11-T3】「蓬莱人形 Round 1」科学

思路

使得最大值最小显然二分，考虑知道最大值该如何检查是否可以满足条件。

设球的数量最大值为 k，则我们需要对所有满足 a_i>k 的球进行移动。此处我们首先要满足 a_i\le 2\times k，因为球最多只能在两个盒子内，根据抽屉原理，当 a_i> 2\times k 时，至少会有一个箱子中的球大于 k 个，则永远不会满足条件。

对于所有满足 a_i>k 的球可以分为以下两种移动方式：

  1. 将多余的球移到一个 B 类盒子中，此时需要移动到 B 类盒子中球的数量即为 a_i-k。

  2. 将一个 A 类箱子 j 中的球移到一个 B 类盒子中，再将 A 类箱子 i 中多余的球移到 A 类箱子 j 中，此时需要移动到 B 类盒子中球的数量即为 a_j。

于是我们将满足 a_i>k 的 a_i-k 和满足 a_j<k 的 a_j 加入一个数组并排序。设满足 a_i>k 的 i 的数量为 cnt，则取该数组前 cnt 小即为最佳移动方案。

我们可以贪心的按照数量从大到小为每个球选择满足大小限制条件且代价最小的盒子。当没有满足条件的盒子时，则表示该情况无解，否则可以求出最小代价。此处选择代价最小的盒子可以采用优先队列维护。

时间复杂度 O(n\log^2n)，可以通过。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[200005];
struct node{
    int b,w;
}b[200005];
bool cmp(node x,node y){
    return x.b>y.b;
}
int check(int mid){
    vector<int> mr;
    int mrs=0;
    for(int i=1;i<=n;i++)
        if(a[i]>mid) mr.push_back(a[i]-mid),mrs++;
    for(int i=1;i<=n;i++)
        if(a[i]<mid) mr.push_back(a[i]);
    sort(mr.begin(),mr.end());
    if(mr.size()==0) return 0;
    if(mr[mr.size()-1]>mid) return -1;
    int r=1,tot=0;
    priority_queue<int,vector<int>,greater<int>> c;
    for(int i=mrs-1;i>=0;i--){
        while(b[r].b>=mr[i]) c.push(b[r].w),r++;
        if(c.empty()) return -1;
        tot+=c.top();c.pop();
    }
    return tot;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i].b>>b[i].w;
    sort(b+1,b+1+m,cmp);
    int l=1,r=1e9,mid,res1=1e9+1,res2=0;
    while(l<=r){
        mid=(l+r)/2;
        int tmp=check(mid);
        if(tmp!=-1) r=mid-1,res1=mid,res2=tmp;
        else l=mid+1;
    }
    cout<<res1<<" "<<res2<<endl;
    return 0; 
}