题解 P1323 【删数问题】

· · 题解

本题使用优先队列求解，这个还是容易的，把返回的最小的数按位分解，然后存在数组里，接下来对数字里的数字进行贪心策略就可以了，贪心最好使用链表，因为链表删除很容易，当然也可以使用数组模拟链表。注意本题的题意，比如输入 9 9 输出应该是 13791517193133 99333 每次删除1个元素，立刻返回，从新从起始位置找到升序的元素，然后删掉。 输入 7 6 输出为： 9719 如果最后都是降序后，如果删除的个数不够的话，就从前往后输出 长度-M 个数字； 注意这句：int len=(int)log10(s)+1; 计算一个数的位数（也就是长度），这是基本知识！

#include <iostream>
#include <queue>
#include <math.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
typedef long long LL;
LL a[600000],next[600000];
int num=0;
struct sa
{
    int w;
    struct sa *next;

};
int main()
{  LL k,m,s,x,y;
int flag=0;
memset(next,0,sizeof(next));
memset(a,0,sizeof(a));
  priority_queue< LL,vector<LL>,greater<LL> > v;
  cin>>k>>m;
  v.push(1);
  x=0;
  while(!v.empty())
  {
    s=v.top();
    v.pop();
    num++;
    v.push(2*s+1);
    v.push(4*s+5);
   int len=(int)log10(s)+1;
    for(int i=len+x;i>x;i--)
    {a[i]=s%10;
     s=s/10;

    }
     x=x+len;

  if (num==k) break;
  }
  for(int i=1;i<=x;i++)
  cout<<a[i];
  cout<<endl;
  struct sa *head,*p,*q;
  head=(struct sa *)malloc(sizeof(struct sa));
  head->w=0;
 q=head;
  for(int i=1;i<=x;i++)
  {
      p=(struct sa *)malloc(sizeof(struct sa));
      p->w=a[i];
      q->next=p;
      q=q->next;

  }
  q->next=NULL;
  int tt=0;
  //int flag=0;
   while(1)
   {
   p=head;
     flag=0;
      while(p->next!=NULL&&p->next->next!=NULL)
       {
         if (p->next->w<p->next->next->w)
        {
          q=p->next;
          p->next=p->next->next;
          free(q);
          tt++;
          flag=1;
          break;

        }
        else
        p=p->next;
        }

  if (flag==0) break;
  if (tt==m) break;
  }

  for(p=head->next;p!=NULL;p=p->next)
    cout<<p->w;
    cout<<endl;
    return 0;
}