P1678 Annoyed College Entrance Examination Volunteers

P1678 Question Bank Links: https://www.luogu.org/problem/P1678

Difficulty: Popularization-

Algorithmic tags: simulation, greed, sorting, binary search

1. Naive simulated O(m*n) score 30

First, the admission scores of m schools are sorted, and then the scores of each examinee are used to find the first university in turn (if the admission score of a university is greater than or equal to that of the examinee, that is, the first university). The examinee's scores are between the admission scores of the first and the second universities, and the scores of the examinee are subtracted from the admission scores of the first and the second universities respectively, and the absolute values are obtained. Because the minimum value is required, the sum is added to the smaller value after the absolute value is taken. Finally, the sum is the answer.

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 int m, n, a[100010], b[100010];
 5 int main()
 6 {
 7     scanf("%d%d", &m, &n);
 8     int sum = 0;
 9     for(int i = 0; i < m; ++i)
10         scanf("%d", &a[i]);
11     for(int i = 0; i < n; ++i)
12         scanf("%d", &b[i]);
13     sort(a, a + m);
14     for(int i = 0; i < n; ++i)
15     {
16         for(int j = 0; j < m; ++j)
17         {
18             if(b[i] <= a[j])
19             {
20                 if(j == 0) sum += a[0] - b[i];
21                 else sum += min(abs(a[j] - b[i]), abs(a[j - 1] - b[i]));
22                 break;
23             }
24         }
25     }
26     printf("%d\n", sum);
27     return 0;
28 } 

2. Binary search optimization O(log(m)*n) score 100

Using binary search to find the first university of each candidate, the search process only needs log(m) times, which can solve the problem of large time complexity. The rest is the same as the simple algorithm.

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 int m, n, a[100010], b[100010];
 5 int main()
 6 {
 7     scanf("%d%d", &m, &n);
 8     int sum = 0;
 9     for(int i = 0; i < m; ++i)
10         scanf("%d", &a[i]);
11     for(int i = 0; i < n; ++i)
12         scanf("%d", &b[i]);
13     sort(a, a + m);
14     for(int i = 0; i < n; ++i)
15     {
16         int l = 0, r = m - 1;
17         while(l < r)
18         {
19             int mid = (l + r) / 2;
20             if(b[i] >= a[mid]) l = mid + 1;
21             else if(b[i] < a[mid]) r = mid;
22         }
23         if(b[i] <= a[0]) sum += a[0] - b[i];
24         else sum += min(abs(a[l - 1] - b[i]), abs(a[l] - b[i]));
25     }
26     printf("%d\n", sum);
27     return 0;
28 } 

Tags: PHP REST

Posted on Thu, 10 Oct 2019 13:38:36 -0700 by Solar