SGU 114 – Partical Sum with Numerical Analysis

/* 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;
}

Leave a Reply

Your email address will not be published.