CF 732 E - Sockets
問題
問題概要
台のコンピュータがあり、それぞれ番目のコンピュータは電力を必要とする。今、会場には個のコンセントがあり、番目のコンセントは電力を供給できる。そして、を満たすときに限って、番目のコンピュータと番目のコンセントを接続することが出来る。
これだと電源につなげるコンピュータが少なすぎるので、アダプタという器具を使ってコンセントから供給される電力を調整することを考える。1つのコンセントにたいしてアダプタは直列に何個でもつなぐことが可能であり、今供給される電力がであるコンセントにアダプタを1つ繋ぐと、供給される電力はになる(例えば、最初が10なら、アダプタを繋ぐごとに10→5→3→2→1→1→...となっていく)。
さて、アダプタを使って同時に台のコンピュータに電力を供給したい。このような方法が複数ある時にはアダプタの個数が最小になるようにしたい。
と、更に番目のコンセントに繋ぐアダプタの個数と番目のコンピュータをどのコンセントに繋ぐべきかを表す番号を示せ。繋ぐ場所がないコンピュータは0を出力せよ。
アイデア
まず、コンピュータの方もコンセントの方も電力の昇順でソートしておく(出力のために、インデックスも保存しておく必要がある)。
さて、コンピュータを昇順に見ていく。それと同時に、そのコンピュータに適切なコンセントの番号も保存しておく。今、番のコンセントが既に使われている、もしくはそのソケットの電力がコンピュータよりも低い時にはを増加させる。もしコンセントの電力が今注目しているコンピュータの電力にマッチするならそのコンセントとコンピュータの接続を決定する。そして、このループが1回終わるごとに、コンセントにアダプタを付ける(つまり、と値を変更する)ことをする。これを全てのコンセントにこれ以上アダプタを付ける意味がなくなるまで繰り返せば、自然と求めたい条件に合致している組み合わせを選び出すことが出来る。
では「全てのコンセントにこれ以上アダプタを付ける意味がなくなる」状況はどんな状況なのかと考えてみると、最終的にはどんなコンセントも大量のアダプタを繋ぐと電力は1に収束していくのでそうなってしまった時になる。つまり、コンセントの中で最大の電力のものをとすれば回繰り返せばよいということが分かる。1回のループにかかる計算量はであるから、全体でとなり、間に合う。
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second typedef pair<int,int> pi; int main() { int n,m; scanf(" %d %d", &n, &m); vector<pi> p(n), s(m); rep(i,n) { scanf(" %d", &p[i].fi); p[i].se=i; } rep(i,m) { scanf(" %d", &s[i].fi); s[i].se=i; } sort(all(p)); sort(all(s)); // a:i番目のコンセントにいくつアダプタを繋ぐか // b:i番目のコンピュータは何番のコンピュータに繋ぐか vector<int> a(m),b(n,-1); vector<bool> used(m,false); rep(adapter,31) { int sidx=0; rep(i,n) { int b_idx=p[i].se; if(b[b_idx]!=-1) continue; while(sidx<m && (s[sidx].fi<p[i].fi || used[sidx])) ++sidx; if(sidx<m && !used[sidx] && s[sidx].fi==p[i].fi) { used[sidx]=true; int a_idx=s[sidx].se; a[a_idx]=adapter; b[b_idx]=a_idx; } } rep(i,m) s[i].fi=(s[i].fi+1)/2; } int c=0,u=0; rep(i,m) u+=a[i]; rep(i,n) if(b[i]!=-1) ++c; printf("%d %d\n", c,u); rep(i,m) { if(i) printf(" "); printf("%d", a[i]); } printf("\n"); rep(i,n) { if(i) printf(" "); printf("%d", b[i]+1); } printf("\n"); return 0; }