首页 > 代码库 > UVa (二分) 11627 Slalom

UVa (二分) 11627 Slalom

2024-07-22 03:21:16   212人阅读

题意：

有宽度相同的水平的n个旗门，水平(纵坐标严格递增)滑行的最大速度为Vh(水平速度可以任意调节)。然后还有S双滑雪板，每双滑雪板的垂直速度一定。

然后求能通过的滑板鞋的最大速度。

分析：

显然，滑雪板的速度越小越容易通过所有的旗门。然后二分找出这个能通过旗门的最大值，最后在滑雪板里面找出这个范围的最大值。

如何判断某个速度可以通过所有的旗门：

第一个旗门处起点可以是任意的，到达第二个旗门的垂直高度时有一个范围，然后和第二个旗门的宽度的范围求交集。如果为∅，则不能通过。否则，继续求到达下一个高度的范围，再和第三个旗门的范围求交集。

 

在敲代码的过程中，judge函数WA掉了，后来看的别人的写法过的。浮点运算尽是坑啊，Orz

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7  8 const int maxn1 = 100000 + 10; 9 const int maxn2 = 1000000 + 10;10 int w, vx, n;11 int x[maxn1], y[maxn1], s[maxn2];12 13 bool judge(int vy)14 {15     int i,j;16     double x1,x2;17     x1=x[0];18     x2=x[0] + w;19     for(i = 1; i < n; i++)20     {21         double d = vx*1.0*(y[i] - y[i-1]) / vy;22         x1 -= d,x2 += d;23         x1 = max(x1, x[i]*1.0);24         x2 = min(x2, (x[i] + w)*1.0);25         if(x1 - x2>1e-10)26         {27             return false;28         }29     }30     return true;31 }32 33 int main(void)34 {35     #ifdef LOCAL36         freopen("11627in.txt", "r", stdin);37     #endif38 39     int T, m, i;40     scanf("%d", &T);41     while(T--)42     {43         scanf("%d%d%d", &w, &vx, &n);44         for(int i = 0; i < n; ++i)45             scanf("%d%d", &x[i], &y[i]);46 47         int L = 0, R = maxn2;48         while(L < R)49         {50             int mid = L + (R - L + 1) / 2;51             if(judge(mid))    L = mid;52             else    R = mid - 1;53         }54 55         int ans = 0;56         scanf("%d", &m);57         for(i = 0; i < m; ++i)58         {59             int x;60             scanf("%d", &x);61             if(x <= L)62                 ans = max(ans, x);63         }64         if(ans)65             printf("%d\n", ans);66         else67             puts("IMPOSSIBLE");68     }69     return 0;70 }
代码君

 

UVa (二分) 11627 Slalom


联系
我们