一道ACM编程题 大概意思是:读入N个数 和一个数T2个人各在N个数中独立的选1个数 求选出的这两个数乘积大于T的概率.
来源:学生作业帮 编辑:作业帮 分类:综合作业 时间:2024/05/05 07:03:25
一道ACM编程题
大概意思是:
读入N个数 和一个数T
2个人各在N个数中独立的选1个数 求选出的这两个数乘积大于T的概率.
我的想法是二分
大概意思是:
读入N个数 和一个数T
2个人各在N个数中独立的选1个数 求选出的这两个数乘积大于T的概率.
我的想法是二分
按照最常规的算法,遍历是难以避免的,而我们的算法则希望尽可能的排除掉一些数以减少遍历的量,所以第一步我认为应该先进行无意义数据的排除,至于排除的方法,我的想法是先排序,然后取这一堆数字中最大的数,然后从最小的数开始与这个最大的数求积,如果积小于T,则这个数就不参与遍历,直到找到乘积大于T的第k小的数,则对剩余数据进行遍历,时间复杂度是N-k的N-k次方,也是比较可观的.
第二步,我们可以采用一些方法减少遍历的时间复杂度,我们可以取T的平方根,对经过第一步的数据进行分组,大于平方根的那组数据互相之间乘积必然大于T,小于平方根的那组数据互相之间乘积必然小于T,那么完全遍历的规模就缩小到了组与组之间进行笛卡尔运算的规模,即a个数据和b个数据两两相乘,时间复杂度是a*b,(a+b=N),此时时间复杂度已经比较可以接受了.
如果数据量特别大,我们也许会需要进行第三步,对于a和b两组数,取a中最大和和b中最小的进行相乘,然后取a中次大的和b中最小的进行相乘.依此类推,继续对数据进行排除.
我描述的应该比较清晰了,acm,当年我手机震动睡过头了,失之交臂啊,祝你成功,而且特别提醒你手机要保持铃声状态.
第二步,我们可以采用一些方法减少遍历的时间复杂度,我们可以取T的平方根,对经过第一步的数据进行分组,大于平方根的那组数据互相之间乘积必然大于T,小于平方根的那组数据互相之间乘积必然小于T,那么完全遍历的规模就缩小到了组与组之间进行笛卡尔运算的规模,即a个数据和b个数据两两相乘,时间复杂度是a*b,(a+b=N),此时时间复杂度已经比较可以接受了.
如果数据量特别大,我们也许会需要进行第三步,对于a和b两组数,取a中最大和和b中最小的进行相乘,然后取a中次大的和b中最小的进行相乘.依此类推,继续对数据进行排除.
我描述的应该比较清晰了,acm,当年我手机震动睡过头了,失之交臂啊,祝你成功,而且特别提醒你手机要保持铃声状态.
一道ACM编程题 大概意思是:读入N个数 和一个数T2个人各在N个数中独立的选1个数 求选出的这两个数乘积大于T的概率.
从一个包含m个数的整型数组中挑出n个数要求这n个数大于等于其他数,其中m>n,m个数各不相同.
Pascal编程:读入N个数,打印其中的最大数及其位置号
从〔0,1〕之间选出两个数,这俩个数的平方和大于1的概率是
C++编程:输入n个数,找出所有大于n 个数的平均值的那些数及最小数
如何求一个数大于另一个数的概率
数学等比数列难题一道 在数1和4之间插入n个实数,使得(n+2)个数构成递增的等比数列,将这(n+2)个数乘积记作Tn,
n个数存放在数组中(n是最大为100的整数),选出所有大于n个数的平均值的那些数.给我程序的代码
从1、2、3、.、2006这2006个数中,选出两个数相加,使它们的和大于2006,有几种选法
c语言编程从输入的n个数中,去掉一个最大数和一个最小数,求剩余数的平均值.
一个数大于另一个数的绝对值,则这两个数的和是( )
从01到49共49个数中依次选出7个数,7个数中至少有一个数是8尾(如08,18.)的概率计算方法?