chronix:
原理：当油管以上和以下的点数量相等时，
油管不穿过任何点时上下移动，总距离不变
穿过任何的点都会增加距离
所以上下点数量相等时为最短

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
    int n;
    cin >> n;
    int temp1, y[n];
    for (int i = 0; i < n; i++){
        cin >> temp1 >> y[i];
    }
    sort(y, y + n);
    int mid = y[n >> 1];
    int result = 0;
    for (int i = 0; i < n; i++){
        result += abs(mid - y[i]);
    }
    cout << result << endl;
}

#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
#include<string>
#include<algorithm>
#include<numeric>
#include<vector>
using namespace std;
typedef struct point POINT;
struct point{
    int x;
    int y;
};
POINT p[10005];
void shortlength(int n)
{
    int min_y = 987654321;
    int max_y = -987654321;
    int min_len_sum = 987654321;
    int len_sum = 0;

    int i = 0;
    int j = 0;
    for (i = 0; i < n; i++)
    {
        if (p[i].y>max_y)
            max_y = p[i].y;
        if (p[i].y < min_y)
            min_y = p[i].y;
    }
    //printf("%d %d\n", max_y, min_y);
    for (i = min_y; i <= max_y; i++)
    {
        len_sum = 0;
        for (j = 0; j < n; j++)
        {
            len_sum += (abs(p[j].y - i));
        }
        if (len_sum < min_len_sum)
            min_len_sum = len_sum;
    }
    printf("%d\n", min_len_sum);



}
int main()
{
    //freopen("data.in", "r", stdin);
    //freopen("data.out", "w", stdout);
    int n = 0;
    int i = 0;
    int len = 0;
    scanf("%d", &n);
    len = n;
    while (n--)
    {
        scanf("%d %d", &p[i].x, &p[i].y);
    //  printf("%d %d\n", p[i].x, p[i].y);
        i++;
    }
    shortlength(len);
    
    
    return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;
int abs(int x)
{
if(x>0)
{
return x;
}
else
{
return -1*x;
}
}
int main()
{
int n,cnt,sum = 0;
int a[10001];
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%*d%d",&a[i]);
}
sort(a+1,a+n+1);
if(n%2==0)
{
cnt=a[n/2];
}
else
{
cnt=a[(n+1)/2];
}
for(int i=1;i<=n;i++)
{
sum+=abs(cnt-a[i]);
}
printf("%d",sum);
return 0;
}

暴力写的，大神勿喷，只是这最后两个点答案真是大，初始化ans=10000000没过。。。
```c++
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

int n,x,tmp = 0,ans = 0x7fffffff;
int y[100010] = {};

/*bool t(int a, int b)
{
if(a > b) return true;
else return false;
}*/

int abs(int a)
{
if(a < 0) return -a;
return a;
}

int main()
{
scanf("%d",&n);
for(int i = 1;i <= n; i++)
scanf("%d%d",&x,&y[i]);
sort(y+1, y+1+n);
for(int i = y[1];i <= y[n]; i++)
{
tmp = 0;
for(int j = 1;j <= n; j++)
tmp += abs(y[j]-i);
if(tmp < ans) ans = tmp;
}
printf("%d\n",ans);
return 0;
}
```

#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int n,y[100010];
long long ans=0;
int main()
{
// freopen("in1.txt","r",stdin);
int x,t;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&x,&y[i]);
sort(y+1,y+n+1);
if(n&1) t=y[n/2];
else t=(y[n/2]+y[n/2+1])/2;
cout<<t<<endl;
for(int i=1;i<=n;i++)
{
cout<<abs(t-y[i])<<endl;;
ans+=abs(t-y[i]);
}
printf("%lld",ans);
return 0;
}

无语了，想着测一下暴力能过几个点，结果……AC了。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 10000;
const int M = N * 2;
int n,x,y,y_max = 0,y_min = M,s = 0xfffffff,A[M + 5];
int main()
{
scanf("%d",&n);
memset(A,0,sizeof(A));
for(int i = 0;i < n;i++)
{
scanf("%d%d",&x,&y);
A[y + N]++;
y_max = max(y_max,y);
y_min = min(y_min,y);
}
for(int i = y_min;i <= y_max;i++)
{
int t = 0;
for(int j = y_min;j <= y_max;j++)
t += A[j + N] * (abs(j - i));
s = min(s,t);
}
printf("%d\n",s);
return 0;
}

顺序统计量，期望为线性
```pascal
uses math;
var a:array[0..10001] of longint;
n,i,m,sum:longint;

function find(b,e,k:longint):longint;
var i,j,x,now,temp:longint;
begin
if (b>=e) then find:=a[b]
else begin
x:=random(e-b)+b;
temp:=a[x];a[x]:=a[e];a[e]:=temp;
x:=a[e];i:=b-1;
for j:=b to e-1 do
if a[j]<=x then begin
inc(i);
temp:=a[j];a[j]:=a[i];a[i]:=temp;
end;
a[e]:=a[i+1];a[i+1]:=x;
now:=(i+1)-b+1;
if now=k then find:=a[i+1]
else if now>k then find:=find(b,i,k)
else find:=find(i+2,e,k-now);
end;

end;

begin
randomize;
read(n);
for i:=1 to n do begin
read(a[i]);read(a[i]);
end;
if n mod 2=0 then m:=(find(1,n,n div 2)+find(1,n,n div 2+1))div 2
else m:=find(1,n,(n+1)div 2);
sum:=0;
for i:=1 to n do begin
inc(sum,abs(a[i]-m));
end;
write(sum);
end.
```

/* ***********************************************
Author        :guanjun
Created Time  :2016/2/18 18:55:02
File Name     :vijosp1691.cpp
************************************************ */
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <list>
#include <deque>
#include <stack>
#define ull unsigned long long
#define ll long long
#define mod 90001
#define INF 0x3f3f3f3f
#define maxn 10000+10
#define cle(a) memset(a,0,sizeof(a))
const ull inf = 1LL << 61;
const double eps=1e-5;
using namespace std;
struct node{
    int x,y;
}nod[maxn];
bool cmp(node a,node b){
    return a.y<b.y;
}
int main()
{
    #ifndef ONLINE_JUDGE
   // freopen("in.txt","r",stdin);
    #endif
    //freopen("out.txt","w",stdout);
    int n;
    while(cin>>n){
        for(int i=1;i<=n;i++){
            cin>>nod[i].x>>nod[i].y;
        }
        ll sum=0;
        sort(nod+1,nod+1+n,cmp);
        int x;
        if(n&1){
            int x=n/2+1;
            x=nod[x].y;
            for(int i=1;i<=n;i++)sum+=abs(nod[i].y-x);
            cout<<sum<<endl;
        }
        else{
            x=(nod[n/2].y+nod[n/2+1].y)/2;
            for(int i=1;i<=n;i++)sum+=abs(nod[i].y-x);
            cout<<sum<<endl;
        }
    }
    return 0;
}

//qsort,奇偶分开亦可
var n,i,j,t:longint;
x,y:array[1..10000] of longint;
ans,tot:real;
procedure qsort(l,r:longint);
var mid,temp,i,j:longint;
begin
i:=l;j:=r;
mid:=y[(l+r) div 2];
repeat
while y[i]<mid do inc(i);
while y[j]>mid do dec(j);
if i<=j then
begin
temp:=y[i];
y[i]:=y[j];
y[j]:=temp;
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
begin
readln(n);
for i:=1 to n do readln(x[i],y[i]);
qsort(1,n);
if (n mod 2)=0 then
begin
t:=n div 2;
ans:=(y[t]+y[t+1])/2;
for i:=1 to n do
begin
tot:=tot+abs(y[i]-ans);
end;
end
else
begin
t:=(n div 2)+1;
ans:=y[t];
for i:=1 to n do
begin
tot:=tot+abs(y[i]-ans);
end;
end;
writeln(tot:0:0);
end.

数据水。。。我直接暴力的a[n div 2-1]到a[n div 2+1]。。。AC了

简单排序找中位数即可，也可用O(n)选择算法，不过懒得编了，，，
#include<iostream>
#include<cstdio>
#include<cmath>
int n,a[10002];
using namespace std;
int merge(int p,int r,int q)
{ int l1,l2,x[10002],y[10002],f=1,g=1;
l1=r-p+1; l2=q-r;
for (int i=1;i<=l1;i++) x[i]=a[p+i-1];
for (int i=1;i<=l2;i++) y[i]=a[r+i];
x[l1+1]=20000; y[l2+1]=20000;
for (int k=p;k<=q;k++)
if (x[f]<y[g]) { a[k]=x[f]; f++;}
else { a[k]=y[g]; g++;}
}

int merge_sort(int p,int q)
{ int r;
if (p<q)
{ r=(p+q)/2;
merge_sort(p,r);
merge_sort(r+1,q);
merge(p,r,q);
}
}
int main()
{ long long t,sum=0;
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d%d",&t,&a[i]);
merge_sort(1,n);
for (int i=1;i<=n;i++) sum+=abs(a[i]-a[(n+1)/2]);
cout<<sum;
}

找中位数铺即可。X轴看都别看。

P1691输油管道问题
Accepted

记录信息

评测状态 Accepted
题目 P1691 输油管道问题
递交时间 2014-11-05 01:35:56
代码语言 C++
评测机 上海红茶馆
消耗时间 622 ms
消耗内存 760 KiB
评测时间 2014-11-05 01:35:58

评测结果

编译成功

foo.cpp: In function 'int main()':
foo.cpp:72:16: warning: overflow in implicit constant conversion [-Woverflow]

测试数据 #0: Accepted, time = 0 ms, mem = 756 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 756 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 760 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 756 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 756 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 752 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 756 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 756 KiB, score = 10

测试数据 #8: Accepted, time = 62 ms, mem = 756 KiB, score = 10

测试数据 #9: Accepted, time = 234 ms, mem = 752 KiB, score = 10

测试数据 #10: Accepted, time = 281 ms, mem = 756 KiB, score = 10

Accepted, time = 622 ms, mem = 760 KiB, score = 110

代码

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>

using namespace std;

int n;
int a;
int i , j , k;
int num[10000 * 2 + 2];
int b[10000 + 2];
int ans[20000 + 2];
int mind;

int min( int a , int b )
{
if( a < b )
return a;
return b;
}

int abs( int x )
{
if( x > 0 )
return x;
return -x;
}

void Qsort( int* s , int l , int r )
{
if( l >= r )
return;
int x = s[ ( l + r ) / 2 ];
int i = l;
int j = r;
while( i < j )
{
while( i < j && s[j] >= x )
j--;
if( i < j )
s[i++] = s[j];
while( i < j && s[i] < x )
i++;
if( i < j )
s[j--] = s[i];
}
s[i] = x;
Qsort( s , l , i - 1 );
Qsort( s , i + 1 , r );
}

int main()
{
while( scanf( "%d" , &n ) != EOF )
{
for( i = 0 ; i < n ; i++ )
{
scanf( "%d %d" , &a , &a );
a += 10000;
num[ a ]++;
}
for( i = 0 , k = 0 ; i <= 20000 ; i++ )
while( num[i] )
{
num[i]--;
b[ k++ ] = i - 10000;
}
for( i = -10000 ; i <= 10000 ; i++ )
for( j = 0 ; j < k ; j++ )
ans[ i + 10000 ] += abs( b[j] - i );
mind = 10000000000;
for( i = 0 ; i <= 20000 ; i++ )
mind = min( mind , ans[i] );
cout << mind << endl;
}
return 0;
}

weak!计数排序。。。

把点投影到y轴上，取中间那个点纵坐标作为管道，再把所有点与中间点的纵坐标之差加在一起

很水啊 不知为何WA 5 6次 =_=

貌似是数据开小了，integer改成longint就过了

var

a:array[-10000..10000]of integer;

n,i,k,tot,x,l:longint;

begin

readln(n);

for i:=1to n do

begin

read(x); readln(x);

inc(a[x]);

end;

for i:=-10000to 10000do

begin

if a[i]<>0then inc(l,a[i]);

if l>=(n+1)div 2 then begin

k:=i;

break;

end;

end;

for i:=-10000 to k-1 do

if a[i]>0then inc(tot,(k-i)*a[i]);

for i:=k+1 to 10000 do

if a[i]>0then inc(tot,(i-k)*a[i]);

writeln(tot);

end.

var a:array[0..10001] of longint;
i,n,ans,num:longint;
procedure qsort(h,l:longint);
var i,j,m,temp:longint;
begin
i:=h;j:=l;m:=a[(i+j) shr 1];
repeat
while a[i]<m do inc(i);
while a[j]>m do dec(j);
if i<=j then
begin
temp:=a[i];a[i]:=a[j];a[j]:=temp;
inc(i);dec(j);
end;
until i>j;
if i<l then qsort(i,l);
if j>h then qsort(h,j);
end;
begin
readln(n);
for i:=1 to n do readln(num,a[i]);
qsort(1,n);
num:=a[n shr 1];
ans:=0;
for i:=1 to n do inc(ans,abs(a[i]-num));
writeln(ans);
end.
这样为什么错了三个点？

不用文件就AC 用了文件就WA0

├ 测试数据 01：答案正确... (0ms, 488KB)

├ 测试数据 02：答案正确... (0ms, 488KB)

├ 测试数据 03：答案正确... (0ms, 492KB)

├ 测试数据 04：答案正确... (0ms, 488KB)

├ 测试数据 05：答案正确... (0ms, 488KB)

├ 测试数据 06：答案正确... (0ms, 488KB)

├ 测试数据 07：答案正确... (0ms, 488KB)

├ 测试数据 08：答案正确... (0ms, 488KB)

├ 测试数据 09：答案正确... (0ms, 488KB)

├ 测试数据 10：答案正确... (0ms, 488KB)

├ 测试数据 11：答案正确... (0ms, 492KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 0ms / 492KB

我罪恶的用了随机快排……

11组数据怎么算的分？

此题难度极高，经鉴定已超过 A+B problem

新手谨慎尝试

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

惭愧啊

三次才过..