枚举算法之售票员

题目大意为：

已知一个国家的售票员人数多于P%少于Q%，问这个国家最少可能有多少人。（黑书p12练习1.2.4）

 

首先这个题可以列出的数学关系式为：

 

设总人数为N，售票员人数为X，则有：

P%*N

 

此时是无法用接不等式的思想去解的，黑书行给了一个例子，如：P=13，Q=14.1，此时最少有15人。

因为0.13*15=1.95 14.1*15=2.115，在1.95跟2.115之间有一整数：2，则此时是可以的。

 

这个关系式就是说，在这之间要至少存在一个整数才可以。所以应该N从1开始慢慢增加，然后逐一判断当N=1，2，3，4。。。这些值时，哪一个是第一个满足这个条件的。

 

 

具体的C语言实现是：

 

我明白了这个思想，但是实现的时候，我有些不知道怎么用代码实现嘿嘿，比如当时不知道怎么挨个去判断（当然是用循环了），然后是怎么判断两个数之间至少有一个整数（我在这些地方，就悲了嘿嘿）

 

#include

using namespace std;

int main()

{

  double p,q;

  cin>>p>>q;

  int s;

  int i;

  int ta,tb;

  while(s=1;;s++) //逐一判断s为1，2，3。。。时哪个第一个满足

  {

       ta=(int)s*p;tb=(int)s*q;

       if((int)ta-(int)tb==1 || (int)ta-(int)tb==-1)//判断之间相差一
           break;

       

  }

 

  cout<

  return 0;

}

 

 

逐一判断s的值是否满足 S*P% —— S*Q% 之间至少有一个整数，我的想法是，直接强制转化为整形，然后相减，差一定是1或-1。

 

但是网上还有一种做法，我觉得很麻烦唉。。。

#include
double a,b;
const double eps=1e-7;
int ans;
int main(){
    std::cin >> a >> b;
    a/=100; b/=100;
    for (ans=0;;ans++){
        double ta=ans*a,tb=ans*b;
        int i;
        for (i=int(ta)-1;i<=int(tb)+1;i++)
            if (i-eps>ta&&i+epsbreak;
        if (i-eps>ta&&i+epsbreak;
        }
    std::cout << ans;
    return 0;
}

阅读(465) | 评论(0) | 转发(0) |

0

上一篇：求【0，1】区间内的均匀分布的随机数

下一篇：贪心算法总结