欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C语言程序设计100例之(30):删数问题

程序员文章站 2022-03-07 15:27:42
例30 删数问题 问题描述 从键盘输入一个高精度正整数num(num不超过250位),任意去掉S个数字后剩下的数字按原先后次序将组成一个新的正整数。编写一个程序,对给定的num和s,寻找一种方案,使得剩下的数字组成的新数最小。 输入格式 num (高精度的正整数)和S(需要删除的数字个数)。 输出格 ......

例30  删数问题

问题描述

从键盘输入一个高精度正整数num(num不超过250位),任意去掉s个数字后剩下的数字按原先后次序将组成一个新的正整数。编写一个程序,对给定的num和s,寻找一种方案,使得剩下的数字组成的新数最小。

输入格式

num (高精度的正整数)和s(需要删除的数字个数)。

输出格式

最后剩下的最小数。

输入样例

51428397

5

输出样例

123

        (1)编程思路。

        由于键盘输入的是一个高精度正整数num(num不超过250位),因此用字符串数组来进行存储。

        为了尽可能地逼近目标,选取的贪心策略为:每一步总是选择一个使剩下的数最小的数字删去,即按高位到低位的顺序搜索,若各位数字递增,则删除最后一个数字,否则删除第一个递减区间的首字符。然后回到串首,按上述规则再删除下一个数字。重复以上过程s次,剩下的数字串便是问题的解了。

        也就是说,删数问题采用贪心算法求解时,采用最近下降点优先的贪心策略:即x1<x2<…<xi<xj;如果xk<xj,则删去xj,得到一个新的数且这个数为n-1位中为最小的数n1,可表示为x1x2…xixkxm…xn。对n1而言,即删去了1位数后,原问题t变成了需对n-1位数删去k-1个数的新问题t′。新问题和原问题相同,只是问题规模由n减小为n-1,删去的数字个数由k减少为k-1。基于此种删除策略,对新问题t′,选择最近下降点的数进行删除,如此进行下去,直至删去k个数为止。

        另外,按这个方法删除s位后,要注意去掉结果中可能存在的前导0。

        (2)源程序。

#include <stdio.h>

#include <string.h>

int main()

{

    char num[251]={'\0'};

    int s,i,j;

    scanf("%s",num);

    scanf("%d",&s);

    while (s>0)    // 循环s次,每次删除一个数字

    {

           i=0;          // 每次删除后从头开始搜寻待删除数字

          while (num[i]!='\0' && num[i]<=num[i+1])

                i++;

         for(j=i;j<strlen(num);j++)

               num[j]=num[j+1];   // 将位置i处的数字删除

        s--;

    }

    i=0;

    while(num[i]=='0') i++;  //处理前导0

    if (num[i]=='\0') printf("0\n");

    else  printf("%s\n",&num[i]);

    return 0;

}

习题30

30-1  删数问题(加强版)

        本题选自洛谷题库 (https://www.luogu.org/problem/ p1323)

题目描述

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

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

输入格式

输入的仅一行,k,m的值,k,m均小于等于30000。

输出格式

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

输入样例

5  4

输出样例

137915

95

        (1)编程思路。

        本题是例30的加强版,主要是先要生成待删除数字的多位数。多位数组成的数字来自给定集合,集合中前30000个元素的生成方法参见“c语言程序设计100例之(14):丑数”中的编程思路。

        生成了多位数后,再按例30的贪心策略进行数字的删除。

        (2)源程序。

#include <stdio.h>

int main()

{

     int h[30001];

     char num[300000]={'\0'},temp[10];

     int k,m,i,j,t,cnt,len;

     scanf("%d%d",&k,&m);

    int p2,p3,min;

   h[1]=1;

    p2=p3=1;

    i=1;

    while(i<k)   

   {

            min=2*h[p2]+1;

            if (min>4*h[p3]+5) min=4*h[p3]+5;

            h[++i]=min;

            if(h[i]==2*h[p2]+1)  p2++;

             if(h[i]==4*h[p3]+5)  p3++;

     }

    len=0;

    for (i=1;i<=k;i++)

    {

        t=h[i];  cnt=0;

        while (t!=0)

        {

            temp[cnt++]=t%10+'0';

            t/=10;

        }

        for (j=cnt-1;j>=0;j--)

            num[len++]=temp[j];

    }

    num[len]='\0';

    printf("%s\n",num);

    cnt=0;       // 删除掉的数字个数

    i=1, j=0;    // 下标i用于遍历字符串,下标j用于保存结果字符串

    while (i<len && cnt!=m)

    {

        if (num[i]<=num[j])     // 不删除,保留到结果串中

            num[++j]=num[i++];

        else

        {

            j--,cnt++;       // 删除结果串中下标j所指字符

            if (j==-1) num[++j]=num[i++];

        }

    }

    while (i<len) num[++j]=num[i++];

    num[++j]='\0';

    printf("%s\n",num);

    return 0;

}

30-2  学生分组

         本题选自洛谷题库 (https://www.luogu.org/problem/ p1109)

题目描述

有n组学生,给出初始时每组中的学生个数,再给出每组学生人数的上界r和下界l (l≤r),每次你可以在某组中选出一个学生把他安排到另外一组中,问最少要多少次才可以使n组学生的人数都在[l,r]中。

输入格式

第一行一个整数n,表示学生组数; n≤50

第二行n个整数,表示每组的学生个数;

第三行两个整数l,r,表示下界和上界。

输出格式

一个数,表示最少的交换次数,如果不能满足题目条件输出-1。

输入样例

2

10 20

10 15

输出样例

5

        (1)编程思路。

        输入n组学生每组人数时累加求出学生总人数sum,若sum<n*l(表示分n组,每组最少l人,总人数不足),或sum>n*l(表示分n组,每组最多r人,总人数超出了,有学生无法放入某一组)时,输出“-1”。

        若能满足条件,则首先要找到人数超过上限的各组*有多少人需要调走,用a进行累计;再找到人数不足下限的各组中所缺少的人数共需要多少人来补,用b进行累计。那么,最优的办法当然是让a去补b,因此a和b谁更大,谁就是需要的最少次数。

        (2)源程序。

#include <stdio.h>

#include <string.h>

int main()

{

    int num[51],n,i,sum,a,b,l,r;

    scanf("%d",&n);

    for (sum=0,i=0;i<n;i++)

    {

        scanf("%d",&num[i]);

        sum+=num[i];

    }

    scanf("%d%d",&l,&r);

    if (sum<n*l || sum>n*r) // 总人数不足或超过

       printf("-1\n");

    else

    {

        a=0;  b=0;

        for (i=0;i<n;i++)

        {

            if (num[i]>r) a+=num[i]-r;

            if (num[i]<l) b+=l-num[i];

        }

        printf("%d\n",a>b?a:b);

    }

    return 0;

}

30-3 宅在家中看电视

问题描述

假设你已经知道了所有你喜欢看的电视节目的转播时间表,你会合理安排,看尽量多的完整节目吗?

输入格式

输入数据包含多个测试实例,每个测试实例的第一行只有一个整数n(n<=100),表示你喜欢看的节目的总数,然后是n行数据,每行包括两个数据ti_s,ti_e (1<=i<=n),分别表示第i个节目的开始和结束时间,为了简化问题,每个时间都用一个正整数表示。n=0表示输入结束,不做处理。

输出格式

对于每个测试实例,输出能完整看到的电视节目的个数,每个测试实例的输出占一行。

输入样例

12

1 3

3 4

0 7

3 8

15 19

15 20

10 15

8 18

6 12

5 10

4 14

2 9

0

输出样例

5

        (1)编程思路。

        定义一个结构体

      struct showtime

      {

           int begin;

           int end;

      };

        用于保存电视节目的开始时间和结束时间。定义结构体数组show[101]保存输入的电视节目情况。

        采用贪心法求解。将电视节目(即结构体数组show)按结束时间从小到大排列(若结束时间相同,则按开始时间从大到小)。

先设lastend=show[0].end,因为第1个元素的结束时间一定是最早的,然后从左到右遍历数组各元素,若当前元素的开始时间大于lastend,则可以看一个完整节目,计数,同时修改lastend使之等于当前元素的结束时间。直到数组全部元素遍历完。

        (2)源程序。

#include <stdio.h>

#include <algorithm>

using namespace std;

struct showtime

{

    int begin;

    int end;

};

bool cmp(showtime a ,showtime b)

{

    if(a.end != b.end)   

        return a.end < b.end;

    else

        return a.begin > b.begin;

}

int main()

{

    showtime show[101];

    int n,i,cnt,lastend;

    while (scanf("%d",&n) && n!=0)

    {

        for (i = 0;i<n;i++)

        {

            scanf("%d%d",&show[i].begin,&show[i].end);

        }

        sort(show,show+n,cmp);    

        cnt = 1;

        lastend = show[0].end;

        for (i = 0;i < n ;i++)

        {

            if(lastend <= show[i].begin)

            {

                cnt++;

                lastend = show[i].end;

            }

        }

        printf("%d\n",cnt);

    }

    return 0;