Codeforces 729C Road to Cinema（二分）

题目链接 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（二分）

最新文章

热门文章