一道ACM编程题 怎么做法?
题目地址:http://acm.tju.edu.cn/toj/showp3495.html大概意思是:读入N个数和一个数T2个人各在N个数中独立的选1个数求选出的这两个数...
题目地址:http://acm.tju.edu.cn/toj/showp3495.html
大概意思是:
读入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,当年我手机震动睡过头了,失之交臂啊,祝你成功,而且特别提醒你手机要保持铃声状态。。。
意法半导体(中国)投资有限公司
2023-06-12 广告
2023-06-12 广告
单片机课程设计是针对《单片机原理及应用技术》课程的一项重要的动手实践活动。该课程设计的目标是让学生通过实际项目的开发,掌握单片机的开发技能,提高解决实际问题的能力,并且加深对单片机原理及应用技术的理解。课程设计的内容包括项目概述、项目要求、...
点击进入详情页
本回答由意法半导体(中国)投资有限公司提供
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询