设有一个数组A：ARRAY[1..N] OF INTEGER；数组中存储的元素为1-N之间的整数，且A[I]≠A[J] (当I≠J)时,(N<=3000)
例如：N=5时，有：（4，3，5，1，2）
此时，数组A的编码定义如下：
A[1]的编码为0：
A[I]的编码为：在A[1]，A[2]，……A[I-1]中比A[I]的值小的元素的个数（I=1，2，……N）
所以上面数组A的编码为:B=(0,0,2,0,1)
现给出一组数，要求出其编码； 给出一组编码,要求你能解码;
输出的数与数之间有一个空格,不能有多余的空格.
输入的第一行是n,m
第二行是n个数,表示数组A;
第三行是m个数,表示这m个数的编码.
输出共两行,第一行是n个数的编码,第二行是m个数的原码.
严格按照要求
求编码这个你应该会的吧
就每个扫过来就行了 n^2的
然后就是解码
我现在只能想到一个比较简单的方法但是可以过
先建一个m个boolean值的数组
全true
然后从最后一个值开始往回推
这个值假如是k 则这个数就是在那个boolean值数组里还是true的值的第k+1个
然后把这个数对应的boolean赋为false
就这样就可以求出来了
附上一小段代码以作解释
var
f:array[1..1000] of boolean;
begin
init;
for i:=m downto 1 do
begin
s:=1;
while b[i]>=0 do
begin
if f[s] then dec(b[i]);
inc(s);
end;
ans[i]:=s-1;
f[s-1]:=false;
end;
就每个扫过来就行了 n^2的
然后就是解码
我现在只能想到一个比较简单的方法但是可以过
先建一个m个boolean值的数组
全true
然后从最后一个值开始往回推
这个值假如是k 则这个数就是在那个boolean值数组里还是true的值的第k+1个
然后把这个数对应的boolean赋为false
就这样就可以求出来了
附上一小段代码以作解释
var
f:array[1..1000] of boolean;
begin
init;
for i:=m downto 1 do
begin
s:=1;
while b[i]>=0 do
begin
if f[s] then dec(b[i]);
inc(s);
end;
ans[i]:=s-1;
f[s-1]:=false;
end;
温馨提示：答案为网友推荐，仅供参考
第1个回答 2010-05-03
这是某年NOIP的题，你可以搜搜看。貌似是96年的。
