Gianthard_陈昱衡 @ 2023-06-29 18:14:09
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdlib>
#include <iostream>
#include <memory>
#include <ostream>
using namespace std;
int m, n;
const int MAX_M = 100005;
const int MAX_N = 100005;
int M[MAX_M], N[MAX_N];
int search(int l, int r, int x) {
while (true) {
// cout<<"l:"<<l<<' '<<"r:"<<r<<endl;
if (r - l <= 2) {
int res = 20000000;
for (int i = l; i <= r; i++) {
if (res > abs(M[i] - x))
res = abs(M[i] - x);
}
return res;
}
int lmid = l + (r - l) / 3;
int rmid = r - (r - l) / 3;
if (abs(M[lmid] - x) <= abs(M[rmid] - x)) {
r = rmid;
} else {
l = lmid;
}
}
}
int main() {
cin >> m >> n;
for (int i = 0; i < m; i++) {
cin >> M[i];
}
// cout<<"m finished"<<endl;
for (int i = 0; i < n; i++) {
cin >> N[i];
}
// cout<<"N finished"<<endl;
sort(M, M + m);
// cout<<"sort finished"<<endl;
// for (int i = 0; i<m; i++) {
// cout<<M[i]<<endl;
//}
long long sum = 0;
for (int i = 0; i < n; i++) {
sum += search(0, m - 1, N[i]);
// cout<<"running"<<i<<endl;
}
cout << sum;
return 0;
}by winner_0207_AFO @ 2023-06-29 18:45:29
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005];
long long ans;
long long find(int num){
int l = 1,r = n;
while(r - l > 1){
int mid = (l + r) >> 1;
if(a[mid] > num) r = mid;
else if(a[mid] < num) l = mid;
else return 0;
}
int t1 = abs(a[l] - num),t2 = abs(a[r] - num);
return t1 < t2 ? t1 : t2;
}
int main(){
cin>>n>>m;
for(int i = 1;i <= n;i++) cin>>a[i];
stable_sort(a + 1,a + 1 + n);
for(int i = 1;i <= m;i++){
int num;
cin>>num;
ans += find(num);
}
cout<<ans;
return 0;
}by winner_0207_AFO @ 2023-06-29 18:46:26
你的太麻烦了
by jiqimaomaomao @ 2023-07-11 17:11:50
三分法？
dalao犇比！本蒟蒻都没听说过