/* Partial Sum & Simple Numerical Analysis * We want to minimize(Sum[Pi*|Xi-d|]) and d is the TV station * Take the absolute away, seperate to 2 parts. * Min(Sum[Pi*(d-Xi)] + Sum[Pj*(Xj-d)]), for 0<i<=k, k<j<=n and Xk<=d<=Xk+1 * Target = d*[Sum(Pi)-Sum(Pj)]-[Sum(PiXi)-Sum(Pj*Xj)] * Target is a linear function, its min value is either on Xk or Xk+1 depend on (Sum(Pi)-Sum(Pj)) >? 0 * Go throughtall the k and we get the answer * Use Partial Sum to speed up, note that we may need long long * Also the original data may not be sorted. */ #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef __int64 LL; typedef struct { LL x,p,c; } City; City city[15005]; LL sumP[15005],sumC[15005]; int n; bool cmp(const City& a, const City& b) { return a.x<b.x; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%I64d %I64d",&city[i].x, &city[i].p); city[i].c = city[i].x * city[i].p; } sort(city+1,city+(n+1),cmp); sumP[0]=0; sumC[0]=0; for(int i=1;i<=n;i++) { sumP[i]=sumP[i-1]+city[i].p; sumC[i]=sumC[i-1]+city[i].c; } LL bestM=-1,bestD,A,B,tmpM; for(int k=1;k<n;k++) { A = sumP[k]-sumP[n]+sumP[k]; B = sumC[n]-sumC[k]-sumC[k]; if(A<0) { tmpM = A*city[k+1].x + B; if(bestM<0 || bestM > tmpM) { bestM = tmpM; bestD = city[k+1].x; } } else { tmpM = A*city[k].x + B; if(bestM<0 || bestM > tmpM) { bestM = tmpM; bestD = city[k].x; } } } if(n==1) printf("%I64d\n",city[1].x); //Note case with only 1 city!! else printf("%I64d\n",bestD); return 0; } |