如果相邻的两个女生以左的男生人数不一样，那么当前女生与其舞伴的距离一定为一，很好想。接着考虑一样的情况，往前找，找到第一个可用男生时，就可以求解了，具体操作见程序。
program vijos1062; var
head,tail,n,i,j,now,cal,k:longint; ans:array[1..1500] of longint; data:array[0..1500] of longint; flag:boolean; begin
readln(N); now:=0;
for i:=1 to n do begin
read(data[i]); end; readln; now:=1;
for i:=1 to n do begin
cal:=data[i]; k:=i-1;
if data[i]=data[i-1] then begin
flag:=false;
while not(flag) do begin
if data[k]=data[i] then begin
dec(cal); dec(k); end;
if (data[i]<>data[k]) and (data[i]-data[k]>data[i]-cal) then flag:=true;
if (data[i]<>data[k]) and (data[i]-data[k]<=data[i]-cal) then begin
dec(cal); dec(k); end; end;
ans[i]:=data[i]-cal+1; end else
begin
ans[i]:=1; end; end;
for i:=1 to n-1 do write(ans[i],' '); writeln(ans[n]); end.
6. 键盘输入一个含有括号的四则运算表达式，可能含有多余的括号，编程整理该表达式， 去掉所有多余的括号，原表达式中所有变量和运算符相对位置保持不变，并保持与原表达式 等价。例：输入表达式 应输出表达式 a+(b+c) a+b+c (a*b)+c/d a*b+c/d a+b/(c-d) a+b/(c-d) 注意输入a+b时不能输出b+a。
表达式以字符串输入，长度不超过２５５。输入不要判错。
所有变量为单个小写字母。只是要求去掉所有多余括号，不要求对表达式化简。 二、算法分析
四则运算表达式含运算符'+','-','*','/','(',')'，其优先顺序由低至高为 '+','-' ─→ '*','/' ─→ '(',')'
一个括号是否作为多余的括号剔除，关键是分析该括号内优先级最低的运算符与左邻括 号或右邻括号的运算符之间的运算优先关系： 设待整理的表达式为(s1 op s2)；
op—括号内优先级最低的运算符('+','-'或'*','/');
１、若左邻括号的运算符为'/'，则无论op为何运算符，括号必须保留，即…… /( s1 op s2)……。因为原式(s1 op s2)作为除数，一旦去除括号后，仅s1作为除数，不 可能与原式等价；
２、若左邻括号的运算符为'*'或'-'，而op为'+'或'-'，则保留括号，即……*-(s1+- s2)。不能去除括号的原因是：
若左邻标符为'*'，优先级大于括号内运算符，因此必须用括号保证括号内的'+'或 '-'优先进行;
若左邻算符为'-'，去除括号后，由于括号内的'+'、'-'要变号， 结果不与原式等 价；
３、若右邻括号的运算符为'*'或'/'，而op为'+'或'-'，原式中的op运算必须优先进行， 因此括号不能去除，即(s1+-s2)*/……；
４、除上述情况外，括号去除，结果与原式等价，即 …s1 op s2…。 我们从最里层嵌套的括号开始，依据上述规律逐步向外层进行括号整理，直至最外层的 括号保留或去除为止。这个整理过程可以用下述的一个递归过程reduce描述： function reduce(表达式串s,var op):string;
{ 整理表达式s,并返回s串中优先级最低的运算符op和整理结果 } begin
if s是变量 then begin
op=' '; reduce=变量s; exit end;
if s是(s')形式 then begin
reduce=reduce(s',op); exit end;
{ s是's1 op s2' 形式 }
a=reduce(s1,c1);b=reduce(s2,c2);
if (op in ['*','-']) and (c2 in ['+','-']) then s2='(s2)'; if (op in ['*','/']) and (c1 in ['+','-']) then s1='(s1)'; if (op in ['/']) and (c2<>' ') then s2='(s2)'; reduce='s1 op s2' end;
例如，剔除表达式'((a+b)*f)-(i/j)'中多余的括号。依据上述算法进行整理的过程如下：
'((a+b)*f)-(i/j)','-'
┌────────┴─────────┐ '((a+b)*f)','*' '(i/j)','/' │ │
'(a+b)*f','*' 'i/j','/'
┌───┴────┐ ┌─┴──┐ '(a+b)','+' 'f',' ' 'i',' ' 'j',' ' │
'a+b','+' ┌┴────┐ 'a',' ' 'b',' '
（图1.1-1）
最后，自底向上得整理结果：(a+b)*f-i/j。
三、程序分析
Program P11; var
ins : string; { 算术表达式 } p : char; { 最低级运算符 }
function suitable(s:string;i:byte):byte;
{ s[i]为')',函数suitable输出与之相对应的'('在s中的位置 } var t:byte;
begin t:=1; repeat dec(i); if s[i]=')' then inc(t)
else if s[i]='(' then dec(t) until t=0; suitable:=i end; {suitable}
function find(s:string):byte;
{ 输出表达式s中最低级算符的位置 } var
i,k:byte; begin
i:=length(s);k:=0; while i>0 do begin
if (s[i]='+') or (s[i]='-') then begin find:=i;exit end; {then}
if (k=0) and ((s[i]='*') or (s[i]='/')) then k:=i; if s[i]=')' then i:=suitable(s,i); dec(i)
end; {while} find:=k end; {find}
function reduce(s:string;var p:char):string;
{ 整理表达式s并返回优先级最低的运算符p } var
a,b:string; { 表达式s的左项和右项整理的结果 }
c1,c2:char; { 表达式s的左项和右项的最低级运算符 } i:byte; { 表达式s的最低级运算符的位置 } begin
if length(s)=1 { 若表达式是变量则返回变量 } then begin
reduce:=s;p:=' ';exit end; {then}
if (s[length(s)]=')') and (suitable(s,length(s))=1)
{ 若表达式被一对括号包住,则返回括号内表达式的整理结果 } then begin
reduce:=reduce(copy(s,2,length(s)-2),p); exit
end; {then}
i:=find(s);p:=s[i]; { 找出最低级运算符及其位置 } a:=reduce(copy(s,1,i-1),c1); { 分别整理左项和右项 } b:=reduce(copy(s,i+1,length(s)-i),c2); { 根据p和c1,c2,决定是否加括号 }
if (p in ['*','-']) and (c2 in ['+','-']) then b:='('+b+')'; if (p in ['*','-']) and (c1 in ['+','-']) then a:='('+a+')'; if (p='/') and (c2<>' ') then b:='('+b+')'; reduce:=a+p+b { 返回整理结果 } end; {reduce}
begin
write('Str = ');
readln(ins); { 输入算术表达式 }
writeln(reduce(ins,p)) { 剔除多余括号并打印整理结果 } end. {main}
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库2014noip复赛模拟练习18（答案）(2)在线全文阅读。
相关推荐：