学步园

题目链接:

http://acm.sgu.ru/problem.php?contest=0&problem=114

题目的意思给定一些X[i] 和 P[i] ,要在X轴上取一点X是的  sum (abs(X[i] - X) *　P[i]) 最小。

可以证明 X必然会为X[i] 中的某一个点，如果不然比如X落在  X[r] 和 X[r +1]之间，那么在X

左面的sum(P[i])　和在X 右面的 sum(P[i]) 必然有一个值大或者小，或者两个相等，如果

有一个大，那么我们可以把X移到sum(P[i])大的那面的那个点上，可以取道更小的值，所以必然

可以将X 放在某一个X[i] 上使得所求的值最小。那么下面我们就可以按X[i]排序，然后O(n)的枚举

所放置的位置来求得答案。

代码如下：

/*<br /> * sgu oj 114<br /> * Accepted: 47ms/0.5s 155kb/4096kb<br /> */<br /> #include "iostream"<br /> #include "cstdlib"<br /> #include "cstdio"<br /> #include "cmath"<br /> #include "algorithm"<br /> using namespace std;</p> <p>const double eps = 1e-6;<br /> const int MaxN = 15005;<br /> int N,pos;<br /> double ans;<br /> const int INF = 0x7fffffff;<br /> typedef struct A{<br /> int X,P;<br /> }A;<br /> bool operator<(const A& a,const A& b){<br /> return a.X < b.X;<br /> }<br /> A AA[MaxN];<br /> void input(){<br /> scanf("%d",&N);<br /> for(int i = 0 ;i < N; ++i)<br /> scanf("%d%d",&AA[i].X,&AA[i].P);<br /> }<br /> double calc(int pp){<br /> double ret = 0;<br /> for(int i = 0 ;i < N; ++i)<br /> ret += fabs(AA[i].X *1.0 -pp)*AA[i].P;<br /> return ret;<br /> }<br /> int solve(){<br /> pos = 0;<br /> int lnum = 0, rnum = 0;<br /> for(int i = 1 ;i < N; ++i)<br /> rnum += AA[i].P;<br /> ans = calc(AA[0].X);<br /> lnum = AA[0].P;<br /> //cout<<"lnum = "<<lnum<<" "<<"rnum = "<<rnum<<endl;<br /> for(int i = 1 ;i < N; ++i){<br /> //long long tmp = calc(AA[i].X);<br /> //cout<<"i = "<<i<<" "<<" tmp = "<<tmp <<endl;<br /> double tmp = ans + 1.0*lnum *(AA[i].X - AA[i-1].X);<br /> tmp -= (1.0*rnum ) * (AA[i].X - AA[i-1].X);<br /> lnum += AA[i].P;<br /> rnum -= AA[i].P;<br /> //cout<<i<<" "<<tmp<<endl;<br /> if(tmp < ans){<br /> ans = tmp;<br /> pos = i;<br /> }<br /> }<br /> return pos;<br /> }<br /> int main(){<br /> // ans = 200000000000000000LL;<br /> //printf("INF = %d/n",INF);<br /> input();<br /> sort(AA,AA + N);<br /> //printf("ret = %d/n",solve());<br /> printf("%.5lf/n",(double)(AA[solve()].X));<br /> return 0;<br /> }<br />