经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
【解题报告】洛谷 P2571 [SCOI2010]传送带
来源:cnblogs  作者:帅小子F$  时间:2018/12/3 10:13:39  对本文有异议

【解题报告】洛谷 P2571 [SCOI2010]传送带
今天无聊,很久没有做过题目了,但是又不想做什么太难的题目,所以就用洛谷随机跳题,跳到了一道题目,感觉好像不是太难。

[CSDN链接](https://blog.csdn.net/Liang_Si_FFF/article/details/84570359)
[题目链接](https://www.luogu.org/problemnew/show/P2571)

===================================================================================
题目描述

在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P,在CD上的移动速度为Q,在平面上的移动速度R。现在lxhgww想从A点走到D点,他想知道最少需要走多长时间

 输入输出格式

输入格式:
输入数据第一行是4个整数,表示A和B的坐标,分别为Ax,Ay,Bx,By

第二行是4个整数,表示C和D的坐标,分别为Cx,Cy,Dx,Dy

第三行是3个整数,分别是P,Q,R

输出格式:
输出数据为一行,表示lxhgww从A点走到D点的最短时间,保留到小数点后2位

 输入输出样例

输入样例#1:
0 0 0 100
100 0 100 100
2 2 1
 输出样例#1:
136.60
说明

对于100%的数据,1<= Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=1000

1<=P,Q,R<=10

======================================================================================================

下面是我的分析过程


分析过程


首先,如图

 


  1. 通过观察题目,我们可以发现,我们行走的路径一定是先在AB边上走,然后走下AB边,走向CD边,然后在CD边上走。(当然,有可能直接在A点就走下了AB边,也有可能直接从D点上了CD边,这里我们同样看作是先走下AB边,然后走上AB边)所以如果我们在AB边取一个点E,在CD边取一个点F,那么,不同的路径就可以用不同的E点和F点唯一表示,即每一个数对(E,F)都唯一对应一条路径(PS:E点可以和A或B重合,F点可以和C或者D重合)所以,我们可以想到一个朴素的算法:枚举E点和F点。但是这种算法明显是太暴力了,不可能通过的。
  2. 我们通过仔细思考,可以这么想:假如我现在的E点是已经确定好是哪个点的了,那么我们的问题就可以转换为:已知一条传送带,以及你在传送带上面的速度和地面上的速度,并且知道起点的准确位置,求到达终点的最短时间。
假如题目变成了这个样子,那么我们会发现,随着F点从C点到D点移动,这个总的时间应该是先递减后递增的。由于是一个单峰函数,所以我们可以用三分来做。
  3. 那么,我们现在的问题就是,这个E点也是移动的。但是我们现在能够做到对于AB边上的每一个点E,都能算出E点固定时的最短时间。所以,相比刚刚开始的同时枚举两个点E和F,现在只需要枚举一下E点就可以了。即:枚举E点的位置,然后对于每一个E点,对F点进行三分,找出每一个E点对应的最小路径的F点是哪一个。
  4. 但是,这个算法好像还是不太好,因为E点的枚举还是很麻烦的,复杂度一样很高。我们可以大胆猜想,或许E点的取值范围也是可以用三分法来做的!但是我还没有想到证明方法,也只是胡乱瞎猜。不过我猜对了。我还没有找到证明,找到证明之后我会再贴链接或者干啥的。
  5. 所以,我们现在可以得出一个能够在规定时间得出答案的算法:先三分E点的位置,对于每一个E点的位置,再三分F点的位置。
(细节注意:由于答案要保留小数点后两位,而地图的最大大小为1000,经过测试,1000乘于2/3大概乘那么30次就可以变得比0.01小,所以我们的三分大概只需要循环30次就可以了。不过我为了安全,循环了40次,反正没差多少。因此,E点需要三分40次,对于每一个E点,需要三分F点40*2次,大概就320次的样子。)
>事实上,这道题除了用三分的做法之外,好像还有什么其他做法,比如模拟退火算法, 但是我还没有学过。
AC代码如下

  1. 1 #include<cstdio>
  2. 2 #include<cmath>
  3. 3 using namespace std;
  4. 4 struct point
  5. 5 {
  6. 6 double x,y;
  7. 7 point()
  8. 8 {
  9. 9 x=y=0;
  10. 10 }
  11. 11 };
  12. 12 double m_abs(double a)
  13. 13 {
  14. 14 return a<0?-a:a;
  15. 15 }
  16. 16 int main()
  17. 17 {
  18. 18 point a,b,c,d;
  19. 19 scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&d.x,&d.y);
  20. 20 double p,q,r;
  21. 21 scanf("%lf%lf%lf",&p,&q,&r);
  22. 22 double result=100000000.0;
  23. 23 point S1=a,S2=b,E1=c,E2=d;
  24. 24 for(int i=1;i<=40;i++)
  25. 25 {
  26. 26 point s1,s2;
  27. 27 s1.x=S1.x+(S2.x-S1.x)/3.0;
  28. 28 s1.y=S1.y+(S2.y-S1.y)/3.0;
  29. 29 s2.x=S2.x-(S2.x-S1.x)/3.0;
  30. 30 s2.y=S2.y-(S2.y-S1.y)/3.0;
  31. 31 double T1,T2;
  32. 32 double X,Y;
  33. 33 X=m_abs(a.x-s1.x);
  34. 34 Y=m_abs(a.y-s1.y);
  35. 35 T1=sqrt(X*X+Y*Y)/p;
  36. 36 X=m_abs(a.x-s2.x);
  37. 37 Y=m_abs(a.y-s2.y);
  38. 38 T2=sqrt(X*X+Y*Y)/p;
  39. 39 E1=c;E2=d;
  40. 40 double T3=10000000.0,T4=100000000.0;
  41. 41 for(int j=1;j<=40;j++)
  42. 42 {
  43. 43 double t1,t2;
  44. 44 point e1,e2;
  45. 45 e1.x=E1.x+(E2.x-E1.x)/3.0;
  46. 46 e1.y=E1.y+(E2.y-E1.y)/3.0;
  47. 47 e2.x=E2.x-(E2.x-E1.x)/3.0;
  48. 48 e2.y=E2.y-(E2.y-E1.y)/3.0;
  49. 49 X=m_abs(s1.x-e1.x);
  50. 50 Y=m_abs(s1.y-e1.y);
  51. 51 t1=sqrt(X*X+Y*Y)/r;
  52. 52 X=m_abs(s1.x-e2.x);
  53. 53 Y=m_abs(s1.y-e2.y);
  54. 54 t2=sqrt(X*X+Y*Y)/r;
  55. 55 X=m_abs(d.x-e1.x);
  56. 56 Y=m_abs(d.y-e1.y);
  57. 57 t1+=sqrt(X*X+Y*Y)/q;
  58. 58 X=m_abs(d.x-e2.x);
  59. 59 Y=m_abs(d.y-e2.y);
  60. 60 t2+=sqrt(X*X+Y*Y)/q;
  61. 61 if(t1>=t2)
  62. 62 {
  63. 63 E1=e1;
  64. 64 T3=t2<T3?t2:T3;
  65. 65 }
  66. 66 else
  67. 67 {
  68. 68 E2=e2;
  69. 69 T3=t1<T3?t1:T3;
  70. 70 }
  71. 71 }
  72. 72 E1=c;E2=d;
  73. 73 for(int j=1;j<=40;j++)
  74. 74 {
  75. 75 double t1,t2;
  76. 76 point e1,e2;
  77. 77 e1.x=E1.x+(E2.x-E1.x)/3.0;
  78. 78 e1.y=E1.y+(E2.y-E1.y)/3.0;
  79. 79 e2.x=E2.x-(E2.x-E1.x)/3.0;
  80. 80 e2.y=E2.y-(E2.y-E1.y)/3.0;
  81. 81 X=m_abs(s2.x-e1.x);
  82. 82 Y=m_abs(s2.y-e1.y);
  83. 83 t1=sqrt(X*X+Y*Y)/r;
  84. 84 X=m_abs(s2.x-e2.x);
  85. 85 Y=m_abs(s2.y-e2.y);
  86. 86 t2=sqrt(X*X+Y*Y)/r;
  87. 87 X=m_abs(d.x-e1.x);
  88. 88 Y=m_abs(d.y-e1.y);
  89. 89 t1+=sqrt(X*X+Y*Y)/q;
  90. 90 X=m_abs(d.x-e2.x);
  91. 91 Y=m_abs(d.y-e2.y);
  92. 92 t2+=sqrt(X*X+Y*Y)/q;
  93. 93 if(t1>=t2)
  94. 94 {
  95. 95 E1=e1;
  96. 96 T4=t2<T4?t2:T4;
  97. 97 }
  98. 98 else
  99. 99 {
  100. 100 E2=e2;
  101. 101 T4=t1<T4?t1:T4;
  102. 102 }
  103. 103 }
  104. 104 T1+=T3;
  105. 105 T2+=T4;
  106. 106 if(T1>=T2)
  107. 107 {
  108. 108 S1=s1;
  109. 109 result=T2<result?T2:result;
  110. 110 }
  111. 111 else
  112. 112 {
  113. 113 S2=s2;
  114. 114 result=T1<result?T1:result;
  115. 115 }
  116. 116 }
  117. 117 printf("%.2f\n",result);
  118. 118 return 0;
  119. 119 }

 


话说这个还是我第一次使用三分呢,以前都没有用过。

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号