P3819 松江1843路

P3819 松江1843路
sigema（r[i]*abs(x[i]-x[s])）;令它最小，是带权中位数问题，s是带权中位数，s左边的r[i]之和+r[s]大于s左边的r[i]之和，反过来也成立。如果sum+r[i]>=总数/2,就break,就找到带权中位数了。

证明的话去百度，很好证明，因为没有理解价值，就没整理。

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<algorithm>

 #include<cmath>

 #include<ctime>

 #include<cstring>

 #define inf 2147483647

 #define For(i,a,b) for(register long long i=a;i<=b;i++)

 #define p(a) putchar(a)

 #define g() getchar()

 //by war

 //2017.10.22

 using namespace std;

 struct node

 {

     long long x;

     long long r;

     bool operator<(const node &aa)const

     {

         return x<aa.x;

     }

 }a[];

 long long n;

 long long s;

 long long L;

 long long ans,sum;

 void in(long long &x)

 {

     long long y=;

     char c=g();x=;

     while(c<''||c>'')

     {

     if(c=='-')

     y=-;

     c=g();

     }

     while(c<=''&&c>='')x=x*+c-'',c=g();

     x*=y;

 }

 void o(long long x)

 {

     if(x<)

     {

         p('-');

         x=-x;

     }

     if(x>)o(x/);

     p(x%+'');

 }

 int main()

 {

     in(L),in(n);

     For(i,,n)

     in(a[i].x),in(a[i].r),s+=a[i].r;

     sort(a+,a+n+);

     s>>=;

     For(i,,n)

     {

         sum+=a[i].r;

         if(sum>=s)

         {

         s=i;

         break;

         }

     }

     For(i,,n)

     ans+=abs(a[s].x-a[i].x)*a[i].r;

     o(ans);

      return ;

 }