P1678 烦恼的高考志愿

P1678题库链接：https://www.luogu.org/problem/P1678

难度：普及-

算法标签：模拟，贪心，排序，二分查找

1.朴素模拟 O(m*n) 得分30

先将m个学校的录取分数线排序，再用每名考生的成绩依次寻找第i个大学(若某个大学的录取分数线大于等于考生的成绩，即为第i个大学)，该考生的成绩在第i-1个与第i个大学的录取分数线之间，用第i-1个和第i个大学的录取分数线分别减去该考生的成绩，取绝对值，因为要求出最小值，则用sum加上两者取绝对值后的较小值，最后sum即为答案

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 int m, n, a[], b[];

 int main()

 {

     scanf("%d%d", &m, &n);

     int sum = ;

     for(int i = ; i < m; ++i)

         scanf("%d", &a[i]);

     for(int i = ; i < n; ++i)

         scanf("%d", &b[i]);

     sort(a, a + m);

     for(int i = ; i < n; ++i)

     {

         for(int j = ; j < m; ++j)

         {

             if(b[i] <= a[j])

             {

                 if(j == ) sum += a[] - b[i];

                 else sum += min(abs(a[j] - b[i]), abs(a[j - ] - b[i]));

                 break;

             }

         }

     }

     printf("%d\n", sum);

     return ;

 } 

2.二分查找优化 O(log(m)*n) 得分100

利用二分查找来找到每名考生的第i个大学，其查找过程只需要log(m)次，可以解决时间复杂度较大的问题，其余与朴素算法同理

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 int m, n, a[], b[];

 int main()

 {

     scanf("%d%d", &m, &n);

     int sum = ;

     for(int i = ; i < m; ++i)

         scanf("%d", &a[i]);

     for(int i = ; i < n; ++i)

         scanf("%d", &b[i]);

     sort(a, a + m);

     for(int i = ; i < n; ++i)

     {

         int l = , r = m - ;

         while(l < r)

         {

             int mid = (l + r) / ;

             if(b[i] >= a[mid]) l = mid + ;

             else if(b[i] < a[mid]) r = mid;

         }

         if(b[i] <= a[]) sum += a[] - b[i];

         else sum += min(abs(a[l - ] - b[i]), abs(a[l] - b[i]));

     }

     printf("%d\n", sum);

     return ;

 }