一题，大家讨论下 [复制链接]

SCU 2006 Warmup Contest 8

B: Water Slides
Submit your solution


Description
It's a hot summer day, and Farmer John is letting Betsy go to the water park where she intends to ride every single slide. The water park has N (1 <= N <= 10,000) platforms (numbered 1..N) from which to enter the M (1 <= M <= 10,000) water slides. Each water slide starts at the top of some platform and ends at the bottom of some platform (possibly the same one). Some platforms might have more than one slide; some might not have any.

The park is very thin, so the platforms lie along a straight line, each platform at a position Xi (0 <= Xi <= 100,000) meters from one end of the park. One walks from one platform to the next via a sidewalk parallel to the line of platforms.

The platforms of the water park are weakly connected; that is, the park cannot be divided into two sets of platforms with no slides running between the two sets. Both the entrance and exit to the park are at platform 1, so Betsy will start and end there.

In order to spend more time on the slides, Betsy wants to walk as little as possible. Find the minimum distance Betsy must travel along the ground in order to try every slide in the park exactly once without repeating.

Input
The input file contains multiple test cases, for each test case:

* Line 1: Two integers, N and M.

* Lines 2..N+1: Line i+1 contains one integer, Xi, the position of platform i.

* Lines N+2..M+N+1: Line i+N+1 contains two integers, Si and Di, respectively the start and end platforms of a slide.

Process till EOF.

Output
For each test case, output:
* Line 1: One integer, the minimum number of meters Betsy must walk.

Sample Input
5 7
5
3
1
7
10
1 2
1 2
2 3
3 1
4 5
1 5
4 1

Sample Output
8

Source
USACO 2006 March

const
maxn=10000;
var
a,l:array[1..maxn]of longint;
n,m,i,j,p,q,min,len:longint;


procedure qsort(p,r:longint);
var i,j,x:longint;
begin
  if p<r then begin
    x:=l[p+random(r-p+1)];
    i:=p-1; j:=r+1;
    while true do begin
      repeat dec(j); until l[j]<=x;
      repeat inc(i); until l>=x;
      if i<j then
      begin
        q:=l;l:=l[j];l[j]:=q;
        q:=a;a:=a[j];a[j]:=q;
      end
      else break;
      end;
    qsort(p,j);
    qsort(j+1,r);
    end;
end;


begin
randomize;
{assign(input,'a.in');reset(input); }
while not(eof) do begin
readln(n,m);
fillchar(a,sizeof(a),0);
for i:=1 to n do read(l);
for i:=1 to m do begin read(p,q);
  inc(a[p]);dec(a[q]);
end;
qsort(1,n);
min:=1; len:=0;
for i:=1 to n do
  if a>0 then
  for j:=min to n do
    if a[j]+a<=0 then begin
    len:=len+abs((l[j]-l)*a);
    a[j]:=a+a[j];min:=j;a:=0;break;end
    else if a[j]<0 then begin
      len:=len+abs((l[j]-l)*a[j]);
      a:=a+a[j];a[j]:=0;
    end;
  writeln(len);
  readln;
end;
end.

引用第0楼勇气les于2006-07-20 14:53发表的“一题，大家讨论下”:
SCU 2006 Warmup Contest 8
B: Water Slides
Submit your solution
.......

如果我看得懂原题的话......

谢谢楼上的，要不然我就连题目都看不懂了~~~

金山快译=误人子弟

用金山译了我都看不懂。。。。

大家把English学好一点，看原文多好

译by sammy312
题目描述
今天是一个炎热的夏日，农民约翰让Betsy去水上公园，因为Betsy想去滑每一个单独的滑水道（我不知道是什么东西）。水上公园有N (1 <= N <= 10,000) 个平台(编号为1..N)，可以进入 M (1 <= M <= 10,000) 个滑水道。每一个滑水道开始于一个平台，结束于另外一个平台(也可能结束于同一平台。)有些平台可能连结着几个滑水道，有些可能一个都不连结。
公园很窄，所以这些平台都在同一直线上，每一个平台离公园的一端相距Xi (0 <= Xi <= 100,000) 米。一个人如果要从一个平台走到另一个平台可以走平行于平台县的人行道。
水上公园的平台连结得很weakly，那就是说，公园里的平台不能划分成两个集合且两个集合间没有水滑道相连。公园的入口和出口都在1号平台，所以Betsy从这里出发。
为了在水滑道上花更多的时间，Betsy想走得尽量少。求出Betsy需要走的最短距离并滑到每一个水滑道不重复也不遗漏。
输入数据
第一行           两个整数N,M.
第2~N+1行       第i+1行有一个整数Xi，第i个平台的位置。
第N+2~M+N-1行   第i+N+1行有两个整数Si和Di，分别表示第i个水滑道的起点和终点。
过程直至EOF。
输出数据
第一行           一个整数，Betsy最少需要走的距离。
样例输入
5 7
5
3
1
7
10
1 2
1 2
2 3
3 1
4 5
1 5
4 1

样例输出
8

来源
USACO 2006 March