集合删数 (vijos 1545) 题解

时间:2021-04-18 19:54:25
【问题描述】

    一个集合有如下元素:1是集合元素;若P是集合的元素,则2 * P +1,4*P+5也是集合的元素,取出此集合中最小的K个元素,按从小到大的顺序组合成一个多位数,现要求从中删除M个数位上的数字,使得剩下的数字最大,编程输出删除前和删除后的多位数字。

注:不存在所有数被删除的情况。

【样例输入】     

    5 4

【样例输出】

    137915

    95

【解题思路】

     首先,我们可以将该问题转化为两个子问题:

     1:求2*p+1与4*p+5两个集合中前k个数组成的数。

     2:求如何删去m个数字使留下的数最大,并输出该数。

    对于子问题1,其实是很好办的,直接将两个集合转化为两个队列,取走两个队列中更小的队首元素,并将其扩展放入到两个集合中,直到取出了k个数。

    那么关键在于如何解决子问题2。

    既然要使留下的数最大,那么自然是越高位越大越好,于是,对于某一个数字是取还是舍,我们应遵循下面两个原则:

    1:如果该数字比其之前的数字大,那么我们应尽量舍去之前的数字。

    2:如果舍去的数字已经有m个了,那就不必舍去了。

    因此,对于每一个数字,我们应把它与它前面的数字进行比较,如果满足上述两个原则,那么就取代其之前的数。详见代码。

【代码实现】

var t,k:array[1..200000] of longint;
    sta:array[0..200000] of char;
    t1,t2,i,n,m,l,top,r1,r2:longint;
    s,st:ansistring;
begin
 readln(n,m);
 i:=1;
 t[1]:=3;
 k[1]:=9;
 t1:=1;
 t2:=1;
 r1:=1;
 r2:=1;
 s:='1';
 while i<n do
  if t[r1]<k[r2] then
   begin
    inc(i);
    str(t[r1],st);
    s:=s+st;
    inc(t1);
    t[t1]:=2*t[r1]+1;
    inc(t2);
    k[t2]:=4*t[r1]+5;
    inc(r1);
   end
  else
   begin
    inc(i);
    str(k[r2],st);
    s:=s+st;
    inc(t1);
    t[t1]:=2*k[r2]+1;
    inc(t2);
    k[t2]:=4*k[r2]+5;
    inc(r2);
   end;
 writeln(s);//解决子问题1
 l:=length(s);
 m:=l-m;
 sta[0]:=chr(57);
 top:=1;
 for i:=1 to l do
  begin
   while(s[i]>sta[top-1])and(top+l-i>m)do//满足两个原则,取代
    dec(top);
   sta[top]:=s[i];
   inc(top);
  end;
 for i:=1 to top-1 do
  if sta[i]<>'0' then
   break;//注意:前导0不要输出
 for i:=i to m do
  write(sta[i]);
 writeln;
end.