読者です 読者をやめる 読者になる 読者になる

AOJ0539 Pizza

なんかWAして悩んだけどよく考えたら確保した配列の要素が一個足りなかっただけだった(泣)
普通にやるとTLEするのでSをsortして配達先に最も近いSを2分探索で決めて足していくだけ

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

int d, n, m, ans, tmp;
int lb, ub, a, b;
int s[100001], del[10001];

int C(int p){
	lb = 0; ub = n + 1;
	while(ub - lb > 1){
		int mid = (lb + ub) / 2;
		if(s[mid] >= p) ub = mid;
		else lb = mid;
	}
	return min(abs(s[ub] - p), abs(s[lb] - p));
}

int main(){
	while(scanf("%d", &d), d){
		ans = 0;
		scanf("%d %d", &n, &m);
		s[0] = 0; 
		s[n + 1] = d;
		for(int i = 1; i < n; i++){
			scanf("%d", &s[i]);
		}
		sort(s, s + n + 1);
		for(int i = 0; i < m; i++){
			scanf("%d", &del[i]);
		}	
		for(int i = 0; i < m; i++){
			ans += C(del[i]);
		}
		printf("%d\n", ans);
	}
	return 0;
}