蓝桥杯2013年第四届真题-买不到的数目（C语言）—— 分段算法（瞎说的，实际上就是骚操作）

解题思路:

1：要采取何种方式去分析出可能的数？

   答：由题中给的数据可以发现，数据量实际不大，每组都有无穷种组合，可实际上只需要分析其前面的一小部分，那么考虑用暴力枚举法，简单粗暴且直观

2：找到何种规律？（以题中给的7、4为例子）最小从7+4=11开始,每组分析7+4=11各数据

如下表格整除用**表示，不可组成用##表示，其他地方用数表示组成

由上表分析就可以得到规律：

1：所有的数是这样组成的：

a.可以组成的数:要么本身能被4、7或4+7整除；要么本身一直减去4+7直到值小于4+7后的能被4或7整除的；

b.不能构成的数：除以上的情况所有的数；

2：由题目得知17是最大的不可构成数，则再往后的4+7位 即22~32不会再出现##

综上所述，解题思路抽象为：

a.每次分析a+b个数，如果里面有不可构造数，则记录值为index（为了更简便，采用从大到小的方式分析），并开始分析下一组数；

b.重复a直到目前组中没有再出现不可构造数；

c：答案为index

参考代码:

#include

int woc(int k,int c,int b)//判断是否为不可构造数，是则返回0，否则1

{

    int flog=0,m=k;

    while(m>=c+b)//数大于c+b时的分析

    {

    if(m%c==0||m%b==0||m%(c+b)==0)

    {

    flog=1;

    break;

    }

    else{

    int l=c+b;

    m-=l;

    }

    }

    if(m%c==0||m%b==0)//数小于c+b时的分析

    {

    flog=1;

    }

    if(flog==1)

    {

    return 0;

    }

    return 1;

}

int main()

{

    int a[2000]={0},c,b;

    scanf("%d %d",&c,&b);

    int flog=0,index=0,j=1;

    flog=(j+1)*(b+c)-1;//每次从一组数中最大的数开始分析

    for(int i=c+b-1;i>=0;i--)

    {

         a[i]=flog;//每轮从最后一位数位开始 

         flog--;//无不可构造数时正常减  

         if(woc(a[i],c,b))//有不可构数时

         {

          index=a[i];//记录位置 

          i=c+b;//检测到则还原 

          j++;//调整倍数 

         flog=(j+1)*(b+c)-1;//调整初始数 （//每次从一组数中最大的数开始分析）

      }

   }

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

    return 0;

}