Solution - P11589
L01001101
·
·
题解
P11589 [KTSC 2022 R2] 寻找魔法珠
首先 0 个普通珠子答案即为 0。
接着考虑每次向袋子中加入珠子。
维护一个小根堆，对于每个袋子记录**加入了下一个珠子**且**魔法珠子在此袋子里**的代价，定义 $cnt_i$ 表示袋子 $i$ 中**当前珠子个数**（即未加入下一个珠子时的个数），$ans_i$ 表示题目所求答案。
那么代价为 $(cnt_i+1)a_i+b_i+ans_{cnt_i}$，也就是加入下一个珠子后，共 $cnt_i+1$ 个珠子，相应的念咒语后代价是 $(cnt_i+1)a_i+b_i$，接着问题转化为 $cnt_i$ 个普通珠子，$1$ 个魔法珠子时，求最坏情况下最小代价，答案即为 $ans_{cnt_i}$。
每次从小根堆中取出堆顶（记堆顶答案为 $x$，代表的袋子为 $t$），那么此时对于 $ans_i$ 分情况讨论。
- 魔法珠子在袋子 $t$ 中，那么代价为 $x$。
- 魔法珠子不在袋子 $t$ 中，那么代价为 $ans_{i-1}$。
取二者中的最劣解（因为是最坏情况下），则有 $ans_i=\max\{ans_{i-1},x\}$。
计算完答案，将 $t$ 袋子珠子数加 $1$（无论魔法珠子在不在袋子 $t$ 中，此时放入 $t$ 袋均最优），更新代价后重新放回小根堆。
时间复杂度 $O(n \log n)$。
讲的有点抽象，结合代码理解。
```cpp
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
typedef pair<LL,int> PLI;
const int N=1e5+10;
int n,m;
int cnt[N];
int d[N];
PLI a[N];
vector<LL> ans;
priority_queue<PLI,vector<PLI>,greater<PLI> > q;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9')ch=='-'?f=0:0,ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return f?x:-x;
}
int count(vector<int> P);
inline PLI f(int i){return PLI((cnt[i]+1)*a[i].first+a[i].second+ans[cnt[i]],i);}//计算袋子 i 加入下一个珠子后的代价
vector<long long> find_minimum_costs(int N,vector<int> A,vector<int> B){
n=N,m=A.size(),ans.push_back(0);
for(int i=1;i<=m;++i)a[i]=PLI(A[i-1],B[i-1]);
std::sort(a+1,a+m+1,[](const PLI &a,const PLI &b){return a.first+a.second<b.first+b.second;}),ans.push_back(a[2].first+a[2].second),cnt[1]=cnt[2]=1;//排序是为了计算 ans[1] 的答案
for(int i=1;i<=m;++i)q.push(f(i));
PLI t;
for(int i=2;i<n;++i)
t=q.top(),q.pop(),ans.push_back(max(ans[i-1],t.first)),++cnt[t.second],q.push(f(t.second));//增加珠子数，更新代价后重新放回小根堆
return ans;
}
//int main(){
// int N=read(),M=read();
// vector<int> A,B;
// for(int i=1;i<=M;++i)A.push_back(read()),B.push_back(read());
// vector<LL> ans=find_minimum_costs(N,A,B);
// for(LL x:ans)printf("%lld\n",x);
// return 0;
//}
```