1. 题目
新兵站队(Soldiers.pas/c/cpp)
题目描述
N个新兵站在警官前面,警官要求向左转,一些士兵向左转,一些向右转了。在这一刻,当一些士兵能看到另一个士兵的脸时,就知道弄错了,然后大家同时又转过去,这都是同时发生的,即每两个碰脸的士兵都是同时发现,而且同时又转过去的。这个过程不断地持续,直到队伍稳定下来。请编程找出这些情况(两个人碰脸,转身)发生了多少次。假如这个过程无穷尽,则输出“NO”。
Formation |
Comments |
Number of turns |
> > < < > < |
Initial formation 初始的队伍 |
2 |
> < > < < > |
One second has passed 1秒过后 |
2 |
< > < > < > |
Two seconds have passed 2秒过后 |
2 |
< < > < > > |
Three seconds have passed 3秒过后 |
1 |
< < < > > > |
Final formation 最终的队列 |
Total: 7 |
输入数据
输入的首行为N(士兵数),其余为符号“>”“ < ”以及回车换行符,总共有N个“< ”“>”符号。每一行可能等于255个字符
1 <= N <= 50 0000
输出数据
输出次数或“NO”
样例输入
6
>><<><
样例输出
7
2. 题目实质
找规律。
3. 算法
想做模拟的孩子们,看看数据范围。
然后,切入正题。
观察,首先,静止时的情况必为 >> 都在右边, << 都在左边,然后,如果情况不限,它必可以,达到上面说的 >> 都在右边, << 都在左边的情况,所以 NO 不存在。
再考虑,若是将一个 < 移到最左边,则他必经过在他左边的所有 > ,因为在他经过时,被他经过的箭头方向会变反,反之亦然,所以,在这里可以直接遍历一遍,统计有多少个 < 需要被移动,以及有每个 > 会被 < 经过多少次,求加和。
另外还有第二种方法:(归并)求逆序对数。( < 看做 1 , > 看做 0 ),核心思想与上面一样。
4. 注意事项
答案非常大,要用 int64 。
5. 程序代码
数学归纳:SueMiller (Pascal)
var n:longint;
ch:char;
i,j,k:int64;
s:array[0..500010]of char;
ans:int64;
function max(a,b:int64):int64;
begin
if a>b then exit(a) else exit(b);
end;
begin
assign(input,'Soldiers.in');reset(input);
assign(output,'Soldiers.out');rewrite(output);
readln(n);
i:=0;
while not seekeof do
begin
repeat
read(ch);
until (ch='<') or (ch='>');
inc(i);
s[i]:=ch;
if i=n then break;
end;
i:=0;
ans:=0;
repeat
inc(i);
if s[i]='>' then inc(j);
if s[i]='<' then inc(k,j);
until i=n;
ans:=k;
writeln(ans);
close(input);close(output);
end.
归并求逆序对: Liukeke (Pascal)
var
a:array[1..500000] of longint;
temp1,temp2:array[1..500000] of longint;
n,i:longint;
ans:qword;
procedure merge(l,r:longint);
var
l1,l2,mid,k,i,j:longint;
begin
mid:=(l+r)>>1;
if l<mid then merge(l,mid);
if mid+1<r then merge(mid+1,r);
l1:=mid-l+1;
l2:=r-mid;
for i:=1 to l1 do
temp1[i]:=a[l+i-1];
for i:=1 to l2 do
temp2[i]:=a[mid+i];
temp1[l1+1]:=maxlongint;
temp2[l2+1]:=maxlongint;
i:=1;
j:=1;
for k:=l to r do
begin
if temp1[i]<=temp2[j] then
begin
a[k]:=temp1[i];
inc(i);
end
else
begin
a[k]:=temp2[j];
inc(j);
inc(ans,l1-i+1);
end;
end;
end;
procedure init;
var
i:longint;
x:char;
begin
readln(n);
for i:=1 to n do
begin
read(x);
if x='>' then a[i]:=1 else a[i]:=0;
end;
end;
begin
assign(input,'soldiers.in');reset(input);
assign(output,'soldiers.out');rewrite(output);
init;
merge(1,n);
writeln(ans);
close(input);
close(output);
end.