【洛谷P1323】删数问题

删数问题

首先找出最小的k个数：用堆每次取出最小的元素p，将p*2+1和p*4+5压入堆。

贪心求最大数：从前往后找第一个data[j+1]>data[j]，删除data[j].（链表应该是比较快的，然而蒟蒻懒得写链表，用了一个数组瞎搞。。不开氧气优化会T一个点）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<queue>
 7 using namespace std;
 8 priority_queue<int,vector<int>,greater<int> > q;
 9 int k,m,a[300010],t,i,j,n;
10 int b[30000010];
11 bool f[30000010];
12 int main()
13 {
14     scanf("%d%d",&k,&m);
15     q.push(1);
16     while(t<k)
17     {
18         int p=q.top();
19         q.pop();
20         int x=2*p+1;
21         int y=4*p+5;
22         q.push(x);
23         q.push(y);
24         a[++t]=p;　　　　//a数组存最小的前k个数
25     }
26     for(i=1;i<=t;i++)
27     printf("%d",a[i]);
28     puts("");
29     for(i=1;i<=t;i++)
30     {
31         int c[10000]={0},sumc=0;
32         while(a[i])
33         {
34             c[++sumc]=a[i]%10;
35             a[i]/=10;
36         }
37         for(j=sumc;j>=1;j--)
38             b[++n]=c[j];　　　//逐个数字地存到b数组中
39     }
40     int cym=0;
41     for(i=1;i<=m;i++)
42     {
43         for(int j=1;j<=n;j++)
44         if(!f[j])　　　　　　//f数组记录是否被删除
45         {
46             int k=j+1;
47             while(f[k]&&k<=n) k++;　　//找到j后面的第一个没被删除的数
48             if(k==n+1) continue;
49             if(b[j]<b[k])　　　　　　　//若b[j]<b[k],删除j
50             {
51                 f[j]=1;
52                 break;
53             }
54         }
55     }
56     for(i=1;i<=n;i++)
57      if(!f[i]) printf("%d",b[i]);
58     return 0;
59 }