题解：P11589 [KTSC 2022 R2] 寻找魔法珠

· · 题解

锐评 loj 的翻译，一些地方都翻译错了，不如 deepseek 机翻。

当 k=0 显然答案为 0。当 k=1 时候要找对答案贡献最小的两个袋子，魔法球在贡献第二小的袋子里。

当 k>1 时候，考虑开一个小根堆，维护所有的袋子如果新加入一个球产生的贡献，每次取贡献最小的袋子加入，和 k-1 时的答案取最大值。

对于每个袋子的贡献，记 t_i 为第 i 个袋子里球的数量，如果新增一颗球对答案的贡献为 a_i\times (t_i+1)+b_i+c_{t_i}。

代码：

#include<bits/stdc++.h>
#include<vector>
#define mp(x,y) make_pair(x,y)
#define ll long long
using namespace std;

ll read(){
    ll x=0,f=1;char ch=getchar_unlocked();
    while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar_unlocked();}
    while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar_unlocked();}
    return f*x;
}

int count(std::vector<int>P);
const int N = 1e6+5;
ll n,m,f[N],cnt[N];
struct Node{ll x,y;bool operator<(const Node a)const{return x+y<a.x+a.y;}}a[N];
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > >pq;

void cmin(ll &x,ll y){if(x>y)x=y;}
void insert(int i){pq.emplace(make_pair(a[i].x*(cnt[i]+1)+a[i].y+f[cnt[i]],i));}

vector<ll> find_minimum_costs(int n, vector<int> A, vector<int> B){
    vector<ll>ans;f[0]=0;m=A.size();cnt[1]=cnt[2]=1;
    for(int i=1;i<=m;i++)a[i]=Node{A[i-1],B[i-1]};
    sort(a+1,a+1+m);f[1]=a[2].x+a[2].y;
    for(int i=1;i<=m;i++)insert(i);
    for(int i=2;i<n;i++){
        auto x=pq.top();pq.pop();
        f[i]=max(f[i-1],x.first);
        cnt[x.second]++;insert(x.second);
    }for(int i=0;i<n;i++)ans.emplace_back(f[i]);
    return ans;
}

// int main(){
//     int n,m;vector<ll>tmp;
//     vector<int>A,B;n=read(),m=read();
//     for(int i=1;i<=m;i++){
//         int x=read(),y=read();
//         A.emplace_back(x),B.emplace_back(y);
//     }tmp=find_minimum_costs(n,A,B);
//     for(ll x:tmp)printf("%lld\n",x);
//     return 0;
// }