CF732E Sockets 题解

功率是 \(x\) 的插座插入一个适配器后功率是 \(y\)，功率是 \(y\) 的插座插入一个适配器后功率是 \(z\)，那么相当于功率是 \(x\) 的插座插入两个适配器。
一个电脑可以用功率小的插座插入较少的适配器表达，也可以用功率大的插座插入较多的适配器表达。这里功率大的插座必然能表达出功率较小的插座。优先使用功率小的插座，就能把功率大的插座和较多的适配器尽可能的节省下来，所以这样是不劣的。
那就从小到大判断每一个插座是否可行：如果可行，就进行分配；如果不可行，那就插入若干个适配器使得能够分配为止；如果最终还是不能分配就跳过下一个。
使用 multimap 和 pair 可以很方便地维护。
初始每个插座可以使用 \([0,\log w]\) 个适配器，每次判断的复杂度为 \(\log n\)，总共有 \(m\) 个插座，总复杂度是 \(\mathcal O(n\log n+m\log m+m\log n\log w)\)。采取 unordered_multimap 即可做到 \(\mathcal O(n+m\log m+m\log w)\)。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#define fi first
#define se second
using std::cin;using std::cout;
using pii=std::pair<int,int>;
constexpr int N=2e5+1;
int n,m,ans1,ans2,r1[N],r2[N];
std::multimap<int,int>s;
pii b[N];
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	std::ios::sync_with_stdio(false);cin.tie(nullptr);
	cin>>n>>m;
	for(int i=1,x;i<=n;i++)
		cin>>x,s.emplace(x,i);
	for(int i=1;i<=m;i++)
		cin>>b[i].fi,b[i].se=i;
	sort(b+1,b+m+1);
	for(int i=1;i<=m;i++)for(int j=0;;j++)
		if(auto it=s.find(b[i].fi);it!=s.end()){
			r1[b[i].se]=j;
			r2[it->se]=b[i].se;
			ans1++;
			ans2+=j;
			s.erase(it);
			break;
		}else{
			if(b[i].fi==1)break;
			b[i].fi=(b[i].fi+1)/2;
		}
	cout<<ans1<<' '<<ans2<<'\n';
	for(int i=1;i<=m;i++)cout<<r1[i]<<' ';
	cout<<'\n';
	for(int i=1;i<=n;i++)cout<<r2[i]<<' ';
	return 0;
}