题目传送门：http://codeforces.com/contest/732/problem/E
这题的费用流做法很显然吧？
但我们可以做得更优：
将插座排序后从小到大进行处理，枚举使用多少次转换器
仔细想一想：如果此时扫描到有未匹配的电脑那么直接匹配不会使答案变劣
于是就这么贪心一下就行啦
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 200000+9;
const double EPS = 1e-8;
struct Socks{
int id,val;
inline bool operator < (const Socks &tmp) const {
return val < tmp.val;
}
}s[N];
int p[N],n,m,nxt[N],num[N],v1[N],v2[N];
map<int,int> head;
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline void insert(int w, int v) {
static int T = 0;
nxt[++T] = head[w]; num[T] = v;
head[w] = T;
}
int main(){
n = read(); m = read();
for (int i=1;i<=n;i++) p[i] = read();
for (int i=1;i<=m;i++) s[i].val = read(), s[i].id = i;
for (int i=1;i<=n;i++) insert(p[i],i);
sort(s+1,s+1+m);
for (int i=1;i<=m;i++) {
for (int w=0,cur=s[i].val;;cur=(int)(ceil((double)cur/2)+EPS),w++) {
if (head[cur]) {
v1[s[i].id] = w;
v2[num[head[cur]]] = s[i].id;
head[cur] = nxt[head[cur]];
break;
}
if (cur == 1) break;
}
}
int vout1 = 0, vout2 = 0;
for (int i=1;i<=m;i++) vout1 += v1[i];
for (int i=1;i<=n;i++) vout2 += (v2[i] > 0);
cout<<vout2<<' '<<vout1<<endl;
for (int i=1;i<=m;i++) printf("%d ",v1[i]); cout<<endl;
for (int i=1;i<=n;i++) printf("%d ",v2[i]);
return 0;
}
Very good info. Lucky me I found your site by chance (stumbleupon).
I have book marked it for later!
Hurrah, that’s what I was looking for, what a material!
present here at this webpage, thanks admin of this website.
My spouse and I absolutely love your blog and find the majority of your post’s to be what precisely I’m looking for.
can you offer guest writers to write content available for you?
I wouldn’t mind publishing a post or elaborating
on a number of the subjects you write in relation to here.
Again, awesome blog!
Everything said was actually very reasonable. But, think on this,
what if you were to write a killer headline? I am not saying your content isn’t good., but suppose
you added a title that grabbed folk’s attention? I mean 【Codeforces 732E】Sockets – Qizy's Database is kinda plain. You ought to glance at Yahoo’s home page and
watch how they create post titles to get viewers to open the links.
You might try adding a video or a pic or two to get people excited about what you’ve written. Just my opinion, it would make your posts
a little bit more interesting.
I like what you guys are usually up too. Such clever work and reporting!
Keep up the terrific works guys I’ve added you guys to my
blogroll.
Thanks for sharing your thoughts about quest bars cheap
coupon twitter. Regards
I really like your blog.. very nice colors & theme.
Did you design this website yourself or did you hire someone to do it for
you? Plz answer back as I’m looking to design my own blog and would like to
find out where u got this from. many thanks
I am regular reader, how are you everybody? This post posted at this web site is
really nice.
Wonderful article! This is the kind of information that should be shared across the net.
Disgrace on the search engines for not positioning this put up higher!
Come on over and discuss with my site . Thank you =)
I know this web page provides quality based content and other material, is
there any other web page which provides these kinds of stuff
in quality?
Hey there! I just wanted to ask if you ever have any issues with hackers?
My last blog (wordpress) was hacked and I ended up losing a
few months of hard work due to no back up. Do you have any solutions to prevent hackers?
Excellent blog right here! Also your website lots
up very fast! What host are you the use of? Can I am getting your associate hyperlink in your host?
I want my web site loaded up as quickly as yours lol
Superb, what a blog it is! This webpage gives useful facts
to us, keep it up.
Its like you learn my thoughts! You appear to know a lot about this, like you wrote the e book in it or something. I believe that you can do with a few p.c. to drive the message house a bit, but instead of that, that is great blog. A great read. I’ll definitely be back.
Hey! Do you know if they make any plugins to help with Search Engine Optimization?
I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good gains.
If you know of any please share. Many thanks!
Very nice write-up. I definitely appreciate this site.
Continue the good work!
Howdy fantastic website! Does running a blog like this take a large amount of work?
I have virtually no expertise in computer programming however I was hoping
to start my own blog soon. Anyways, if you have any
suggestions or techniques for new blog owners please share.
I know this is off topic but I just wanted to ask. Thank you!
Hey there just wanted to give you a quick heads up.
The text in your article seem to be running off the screen in Firefox.
I’m not sure if this is a format issue or something to do with browser compatibility but I thought I’d post to
let you know. The layout look great though! Hope you get the issue fixed soon. Cheers
Just want to say your article is as astounding. The clearness in your post is simply nice and
that i can suppose you’re a professional in this subject.
Fine with your permission let me to clutch your feed to keep updated with drawing close post.
Thank you a million and please keep up the rewarding work.
I’m really loving the theme/design of your blog. Do you ever run into any browser
compatibility problems? A couple of my blog audience have complained about my website not operating correctly in Explorer but looks great in Firefox.
Do you have any solutions to help fix this problem?
If you desire to obtain much from this piece of writing then you have to apply these methods to your
won webpage.
I was suggested this website by my cousin. I’m not sure
whether this post is written by him as nobody else know such detailed about my trouble.
You are incredible! Thanks!
What i do not realize is in reality how you’re now
not actually a lot more smartly-preferred than you may be right now.
You’re so intelligent. You already know thus significantly relating to
this matter, made me personally consider it from a
lot of numerous angles. Its like women and men aren’t involved until it’s something
to do with Girl gaga! Your individual stuffs nice.
Always care for it up!
Wow that was strange. I just wrote an incredibly long comment but
after I clicked submit my comment didn’t appear. Grrrr…
well I’m not writing all that over again. Anyhow, just wanted to say excellent blog!
Way cool! Some very valid points! I appreciate you writing this
post and the rest of the website is also really good.
Appreciate it for all your efforts that you have put in this. very interesting info .