POJ2182 逆推数列

2019-11-06 07:20:52

字体：大中小

来源：转载

供稿：网友

LOST COWSN (2 <= N <= 8,000) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood 'watering hole' and drank a few too many beers before dinner. When it was time to line up for their evening meal, they did not line up in the required ascending numerical order of their brands.Regrettably, FJ does not have a way to sort them. Furthermore, he's not very good at observing PRoblems. Instead of writing down each cow's brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow in line that do, in fact, have smaller brands than that cow. Given this data, tell FJ the exact ordering of the cows. Input* Line 1: A single integer, N * Lines 2..N: These N-1 lines describe the number of cows that precede a given cow in line and have brands smaller than that cow. Of course, no cows precede the first cow in line, so she is not listed. Line 2 of the input describes the number of preceding cows whose brands are smaller than the cow in slot #2; line 3 describes the number of preceding cows whose brands are smaller than the cow in slot #3; and so on.Output* Lines 1..N: Each of the N lines of output tells the brand of a cow in line. Line #1 of the output tells the brand of the first cow in line; line 2 tells the brand of the second cow; and so on.Sample Input

51210Sample Output24531 题目大意：告诉你每只奶牛x左边有几头编号比它小的，让你给出每只奶牛原来的位置。看了下网上的题解，都是树状数组什么的，不是很能理解，因为N^2时间就够了，而N只有8000看一下大致算法。（以下讨论内容均为正整数）
对于奶牛x(x＞1) ，给出了n[x](n[x]＜x)
代表奶牛x站位左边有n[x]头奶牛的编号比x小。
要求给出每个奶牛的站位。
算法清晰:
显而易见，若最大奶牛编号是maxn
maxn站位就是n[maxn]+1。
令此站位=u。
这样的话，对于maxn-1，作出如下讨论
易得
n[maxn-1]＜u-1，站位为n[maxn-1]+1
n[maxn-1]=u-1，站位为u+1.
n[maxn-1]＞u-1，站位为n[maxn-1]+2.
推出奶牛maxn-1的站位后，同理，可以推出maxn-2的位置，
但是情况种数变多，因为已经确定了两头奶牛，它们之间的一段也可以是maxn-2的站位。
那么看到，在最坏情况下，我们需要寻找maxn-1头奶牛的位置(最后一头可以推出)，
而对于当前寻找i奶牛，需要比较maxn-i头奶牛以及自己的常数时间O(1)。
我们定义:
sigma(a,b)=a×(maxn-a+1)+...+b×(maxn-b+1)
当然上式中a＜b。
时间复杂度
O(sigma(1,maxn))=O(maxn²)
代码也很短。
var n,i,t,j:longint;    a,b,c:array[0..8005] of longint;begin  readln(n);  for i:=2 to n do     readln(a[i]);  for i:=n downto 1 do  begin    t:=a[i];    for j:=1 to n do    begin      if b[j]=1 then t:=t+1;       //当有阻碍，阻碍的奶牛编号肯定比i大，直接跳过它就好了      if t<j then break;    end;    c[i]:=j;      //根据上述分析，奶牛i的站位就是最后break的j；能够说明t<j这句话一定会在某一时刻true并且返回一个正确的j，请自行证明    b[j]:=1;  end;  for i:=1 to n do    writeln(c[i]);end.