题目链接 http://codeforces.com/problemset/problem/729/C

题意：n个价格c[i]，油量v[i]的汽车，求最便宜的一辆使得能在t时间内到达s，路途中有k个位置在g[i]的加油站，可以免费加满油，且不耗时间。每辆车有两种运行模式可以随时切换：1.每米一分钟两升油；2.每米两分钟一升油。

看到10^5次加上循环两次就想到二分或者线段树或者看错题意了。

这题二分查找一下汽油就可以了，找到最少多少汽油够到达，然后再for一遍找汽油量大的且价格便宜的车即可。

还有一些关系要注意一下的

t(min) = 不符合 (L > v[i])

          = L (2 * L <= v[i])

          = 3 * L - v[i] (L<=v[i]<2 * L)

#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int M = 2e5 + 10;typedef long long ll;struct TnT {    int v , f;}sl[M];ll pos[M] , sp[M];bool cmp(TnT a , TnT b) {    return a.f > b.f;}int main(){    int n , k , s , t;    scanf("%d%d%d%d" , &n , &k , &s , &t);    for(int i = 0 ; i < n ; i++) {        scanf("%d%d" , &sl[i].v , &sl[i].f);    }    ll le = 0;    int temp = 0;    for(int i = 0 ; i < k ; i++) {        scanf("%I64d" , &pos[i]);    }    sort(pos , pos + k);    for(int i = 0 ; i < k ; i++) {        sp[temp++] = pos[i] - le;        le = pos[i];    }    if(pos[k - 1] != s) {        sp[temp++] = s - le;    }    sort(sl , sl + n , cmp);    int l = 0 , r = n - 1;    int flag;    while(l <= r) {        int mid = (l + r) >> 1;        ll sum = 0;        flag = 0;        for(int i = 0 ; i < temp ; i++) {            ll gg = sp[i] * 3;            if(sl[mid].f < sp[i]) {                flag = 1;                break;            }            else {                if(2 * sp[i] <= sl[mid].f) {                    sum += sp[i];                }                else {                    sum += (gg - sl[mid].f);                }                flag = 0;            }        }        if(flag == 1) {            r = mid - 1;            continue;        }        if(sum > t) {            r = mid - 1;        }        else {            l = mid + 1;        }    }    if(l - 1 == -1) {        printf("-1\n");    }    else {        int MIN = sl[l - 1].v;        int cmper = sl[l - 1].f;        for(int i = 0 ; i < n ; i++) {            if(sl[i].f >= cmper) {                MIN = min(MIN , sl[i].v);            }        }        printf("%d\n" , MIN);    }    return 0;}

Codeforces 729C Road to Cinema（二分）