- C++
二分查找和二分答案
- 2024-8-19 9:32:54 @
1 条评论
-
mrhowe SU @ 2024-8-19 11:32:18
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int m,n,a[N],b[N]; long long sum=0; int bmy(int k){ int l=0,r=m-1; while(l<r){ int mid = (l+r+1)/2; if(a[mid]>k) r=mid-1; else if(a[mid]==k) return 0; else l=mid; // cout<<"1 "<<l<<" "<<r<<endl; } int ll=l; l=0,r=m-1; while(l<r){ int mid = (l+r)/2; if(a[mid]>k) r=mid; else if(a[mid]==k) return 0; else l=mid+1; // cout<<"2 "<<l<<" "<<r<<endl; } int rr=l; // cout<<k<<" "<<a[ll]<<" "<<a[rr]<<endl; return min(abs(k-a[ll]),abs(a[rr]-k)); } int main(){ cin>>m>>n; for(int i=0;i<m;i++)cin>>a[i]; sort(a,a+m); for(int i=0;i<n;i++)cin>>b[i]; for(int i=0;i<n;i++){ sum+=bmy(b[i]); } cout<<sum; return 0; } }
- 1