codeforces 732E（贪心）

题目链接：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 ;

 }