uva 11627 Slalom

点击打开链接uva 11627

思路：二分答案
分析：
1 给定S个滑雪板的速度，问是否可以找到一个滑板使得通过所有的门的时间最少，如果找不到输出IMPOSSIBLE
2 很明显的二分题目，我们知道了二分那应该怎么判断是否可以通过所有的门呢？题目告诉我们向下的速度和水平的最大速度，那么我们就可以利用向下的速度和两个们之间的高度求出下落的时间，那么知道了时间就可以求出水平的最大范围，从而判断下一个门是否在这个区间之内即可
3 注意二分得到的最大值后我们还需要在原来的区间去找ans，因为二分到的答案不一定在原来的数组里面所以应该要去判断一下

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 1000010;
struct Point{
   double left;
   double right;
   double high;
};
Point p[MAXN] , tmp[MAXN];
int W , V , N , S;
int speed[MAXN];

bool isOk(int s){
    double left , right;
    for(int i = 0 ; i < N-1 ; i++){
       double t = (p[i+1].high-p[i].high)*1.0/s;
       left = p[i].left - t*V;
       right = p[i].right + t*V;
       if(p[i+1].right < left || p[i+1].left > right) 
           return false;
       p[i+1].left = max(p[i+1].left , left);
       p[i+1].right = min(p[i+1].right , right);
    }
    return true;
}                                                                               

int solve(){
    sort(speed , speed+S);
    int left , right , mid;
    left = speed[0] , right = speed[S-1];
    memcpy(tmp , p , sizeof(tmp));
    while(left <= right){
        mid = (left+right)>>1;
        if(isOk(mid))
           left = mid+1;
        else
           right = mid-1;
        memcpy(p , tmp , sizeof(p));
    }
    return right < speed[0] ? 0 : right;
}

int main(){
    int Case;
    scanf("%d" , &Case);
    while(Case--){
       scanf("%d%d%d" , &W , &V , &N);
       for(int i = 0 ; i < N ; i++){
          scanf("%lf%lf" , &p[i].left , &p[i].high);
          p[i].right = p[i].left + W;
       }
       scanf("%d" , &S);
       for(int i = 0 ; i < S ; i++)
          scanf("%d" , &speed[i]);
       int ans , tmp = solve();
       if(tmp) {
          ans = 0;
          for(int i = 0 ; i < S ; i++){
             if(speed[i] <= tmp)//查找小于tmp的最大值即为ans
                ans = max(ans , speed[i]);
          }
          printf("%d\n" , ans);
       }
       else printf("IMPOSSIBLE\n");
    }
    return 0;
}