C语言程序设计100例之（30）：删数问题

例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;

}