题目链接:http://codeforces.com/contest/732/problem/E

题意:有n台计算机,m个插座,每台计算机有一个值a[i],每个插座有一个值b[i],每个插座最多只能对应一台计算机,且只有a[i] == b[j]时才能配对。现有无限台适配器,适配器能使b[i]减半,求最多能使多少计算机与插座配对(c),以及对应的最小的适配器个数(u)(即先考虑c最大,再使u最小)。

思路:先对计算机和插座按值排序,不断减半,发现能配对就配对。

 #include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + ;
int a[N],b[N],c,u;
struct node
{
int val,id;
node(){}
node(int v,int i) : val(v),id(i) {}
bool operator < (const node &t)
{
if(val != t.val)
return val < t.val;
return id < t.id;
}
}p[N],s[N];
map <int,int> mp;//计算机值出现的次数
int main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i = ; i <= n; i++)
{
scanf("%d",&p[i].val);
p[i].id = i;
mp[p[i].val]++;
}
sort(p + , p + n + );
for(int i = ; i <= m; i++)
{
scanf("%d",&s[i].val);
s[i].id = i;
}
sort(s + , s + m + );
for(int i = ; i <= m; i++)
{
for(int j = ; j < ; j++)
{
if(mp.count(s[i].val))//发现可能匹配
{
int t = lower_bound(p + , p + n + , node(s[i].val,)) - p + mp[s[i].val] - ;//找到位置(由于有可能有多个相同的值,这里先从最后一个开始往前推)
if(p[t].val == s[i].val && !b[p[t].id])//值相等 && 该计算机还未匹配
{
b[p[t].id] = s[i].id;
mp[s[i].val]--;//数量-1
a[s[i].id] = j;
c++;
u += j;
break;
}
}
s[i].val = (s[i].val + ) >> ;
}
}
printf("%d %d\n",c,u);
for(int i = ; i <= m; i++)
printf("%d ",a[i]);
printf("\n");
for(int i = ; i <= n; i++)
printf("%d ",b[i]);
return ;
}
05-04 08:49