pascal题目：游戏
上了半天的物理数学课，大家的脑子有点转不动了，下午的课表似乎看透了同学们的 心思，第一节就安排了体育课，CZ 中学的课表真是太有爱了，赞一个！午间休息后，文体 委员小 S 喊大家到教室外的走廊上排队，队形整好后小 S 带着大家走到了大操场上，体育 老师早就在那等着了，他先安排同学们做了五分钟的准备活动，接下来让大家玩一个有趣 的游戏，在这个游戏里，全班同学先散开站在操场上，同学们轮流玩这个游戏，从 1 号同学开始，然后是 2 号 3 号等等 （只要这个同学仍然参与这个游戏）。每次轮到玩的同学，就选择一个目前离他最近的同学，走过去拍他一下，然后回到原来的位置，那个被拍到的 同学就被排除在游戏之外了，必须立刻离开操场。当操场上只剩下一个同学时，游戏即告 结束，最后站在操场上的那个同学就是赢家。
R 老师 正和隔壁班的 F 主任津津有味地在场边看着同学们做游戏，为了添加一点乐 趣，R 老师就和 F 主任打赌哪个同学会赢？所以他想事先知道谁是赢家。R 老师希望你写 一个程序，读入同学们相互之间的距离，模拟出哪个同学最终会获胜。
输入
输入数据第一行为一个正整数 N， 表示在操场上玩游戏的人数，其中 1≤N≤1000， 接下来共有 N 行数据，每行有 N 个用空格隔开的整数，其中第 i 行第 j 列的数据表示操场 上编号为 i 的同学与编号为 j 的同学之间的距离。输入数据保证第 i 行第 i 列（主对角线 上的位置）的数据均为 0，其余数据均为正整数，且第 i 行第 j 列的数据一定等于第 j 行 第 i 列的数据，这意味着同学甲到同学乙的距离等于同学乙到同学甲的距离；操场上任意 两对同学之间的距离均不相同，也就是说上三角部分的正整数互不相同。
输出
输出数据仅有一行包含一个正整数表示获胜的同学的编号。
样例输入
4
0 1 6 3
1 0 4 5
6 4 0 2
3 5 2 0
样例输出
1
提示
样例解释
1 号同学先玩，走过去拍了离他最近的 2 号同学，2 号同学被排除出游戏；接下去就
直接轮到 3 号同学玩了，他走过去拍了 4 号同学，4 号同学被排除出游戏；再次轮到 1 号
同学时，他走过去拍了 3 号同学，3 号同学被排除出游戏。最后 1 号同学获胜。
数据范围
30%的数据满足：n≤10
60%的数据满足：n≤100
100%的数据满足：n≤1000，所有数据不超过长整型范围 展开
这题也许是贪心算法的一个简单应用 。
一开始我是这么想的：
但是马上就推翻了这种简单的算法：
如果给第一个人7颗糖，第二个人3颗，那么生气指数是：
尽管上述看似对于解题没太大帮助，但是了解一个思考过程我觉得也是有必要的。
事实上，它启发了我找到下面这个应该正确的算法。
——————————————————————————————————————
36，比一开始的55小了很多。
事实上，经过验证，36是这一个例子中最小的结果。
（用以上算法验证一下样例，得到的也是正确答案）
贪心的算法一旦确定，代码应该就好写了。
目前摆在面前的一道坎，是数据范围。那么大的数，一个个减去一定会超时，因此用了一点技巧。
写了很久的代码，看一下：
var a:array[1..100000]of record
x,y:longint; //记录类型，x表示理想糖数，y表示实际收到糖数；
end;
s,ans:int64;
m,n,i,j,t:longint;
procedure sort(l,r:longint); //快速排序，从小到大；
var i,j,k,t:longint;
begin
i:=l; j:=r; k:=a[(l+r) div 2].x;
repeat
while a[i].x<k do inc(i);
while a[j].x>k do dec(j);
if i<=j then
begin
t:=a[i].x; a[i].x:=a[j].x; a[j].x:=t;
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
begin
readln(m,n);
for i:=1 to n do
begin
readln(a[i].x);
a[i].y:=a[i].x;
inc(s,a[i].x);
end;
sort(1,n);
for i:=1 to n do a[i].y:=a[i].x;
i:=0;
while true do
begin
inc(i);
t:=a[i].y;
while (s-t*(n-i+1)<m) and (t>0) do
dec(t);
dec(s,t*(n-i+1));
if t>0 then for j:=i to n do dec(a[j].y,t)
else break;
end; //代码核心；
while s>m do
begin
dec(a[i].y);
inc(i);
dec(s);
end;
for i:=1 to n do
inc(ans,trunc(sqr(a[i].x-a[i].y)));
writeln(ans); //最终结果；
readln;
end.
或者直接从附件中下载。
望采纳，谢谢
var
hash : array[0..1000] of boolean;
d : array[0..1000,0..1000] of longint;
i,j,n,x : longint;
begin
readln(n);
for i := 1 to n do
for j := 1 to n do read(d[i,j]);
for i := 1 to n do d[i,i] := 1 << 30;
for i := 1 to n do d[0,i] := 1 << 30;
for i := 1 to n do
if not hash[i] then
begin
x := 0;
for j := 1 to n do
if (j <> i) and not hash[j] and (d[x,i] > d[j,i]) then
x := j;
hash[x] := true;
end;
for i := 1 to n do if not hash[i] then break;
writeln(i);
end.
=====================================================================================
7
0
1 0
6 4 0
3 5 2 0
9 7 8 10 0
11 12 13 14 15 0
19 17 16 20 18 21 0
======================================================================================
const max=31999;
var
n:integer;
a:array[1..1000,1..1000] of integer;
m:array[1..1000] of boolean;
i,j,k,min,num:integer;
p,q:integer;
f:textfile;
begin
assign(f,'game_one.txt'); reset(f);
readln(f,n);
for i:=1 to n do for j:=1 to i do read(f,a[i,j]); //只要求输入下三角阵
close(f);
for i:=1 to n-1 do for j:=i+1 to n do a[i,j]:=a[j,i]; //形成方阵
for i:=1 to n do begin for j:=1 to n do write(a[i,j]:4); writeln; end;
writeln;
for i:=1 to n do m[i]:=true;
for i:=1 to n do a[i,i]:=max;
k:=1;
repeat
min:=31990;
for i:=1 to n do if a[k,i]<min then begin min:=a[k,i]; j:=i; end;
m[j]:=false;
for i:=1 to n do begin a[j,i]:=max; a[i,j]:=max; end;
num:=0;
for i:=1 to n do if m[i] then inc(num);
if num>1 then begin
inc(k); if k>n then k:=1;
while not m[k] do begin
inc(k);
if k>n then k:=1;
end;
end;
for p:=1 to n do begin for q:=1 to n do write(a[p,q]:6); writeln; end;
writeln;
until num=1;
for i:=1 to n do if m[i] then writeln(i);
end.
