[2014-11-07 模拟赛] number(number.cpp/pas)

描述 Description

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

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

输入格式 InputFormat

输入仅一行,K,M 的值,K,M 均小于等于 30000。

输出格式 OutputFormat

输出为两行,第一行为删除前的数字,第二行为删除后的数字。

样例输入 SampleInput

5 4

样例输出 SampleOutput

137915
95


NOIP 模拟赛


代码 Code

维护一个单调递增栈,如果还没删够则从后往前删。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=30005;
int i,j,t,n,m,l,r,k,z,y,x;
int a[maxn];
char ans[maxn*10],ch[maxn*10];
int main()
{
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    scanf("%d%d",&k,&m);
    a[1]=1;
    n=l=r=1;
    while (n<k)
    {
        if (a[l]*2+1<=a[r]*4+5)
        {
            a[++n]=a[l]*2+1;
            l++;
        }
        else
        {
            a[++n]=a[r]*4+5;
            r++;
        }
    }
    l=0;
    for (i=1;i<=k;i++) printf("%d",a[i]);
    printf("\n");
    for (i=k;i>0;i--)
    {

        while(a[i]>0)
        {
            ch[++l]=a[i]%10+'0';
            a[i]/=10;
        }
    }
    r=0;
    for (i=l;i>0;i--)
    {
        while (r>0 && m>0 && ch[i]>ans[r]) 
        {
            r--;
            m--;
        }
        ans[++r]=ch[i];
    }
    if (m>0) r-=m;
    for (i=1;i<=r;i++) printf("%c",ans[i]);
    printf("\n");
    return 0;
}