自动搬运

查看原文

来自洛谷，原作者为

	L01001101 The world is splendid and grand, welcome home.

搬运于2025-08-24 23:08:38，当前版本为作者最后更新于2025-02-18 16:42:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P11589 [KTSC 2022 R2] 寻找魔法珠

首先 $0$ 个普通珠子答案即为 $0$。

$1$ 个普通珠子的答案即为 $m$ 个袋子中第 $2$ 小的 $a_i+b_i$（将普通珠子和魔法珠子分别装入代价前两小的袋子，最坏情况下即魔法珠子在代价第二小的袋子中）。

接着考虑每次向袋子中加入珠子。

维护一个小根堆，对于每个袋子记录加入了下一个珠子且魔法珠子在此袋子里的代价，定义 $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)$。

讲的有点抽象，结合代码理解。

#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;
//}