Codeforces Round #380 (Div. 2) C. Road to Cinema 预处理+二重二分法+贪心

Source

Codeforces Round #380 (Div. 2, Rated, Based on Technocup 2017 - Elimination Round 2)

My Solution

题意：从出发点0到目标点s，经过k个加油站，每个加油站可以在瞬间把车子的油箱加油加满，然后有n辆车子可以选择，每辆车有两个属性c、v分别表示花费、油箱容量，

此外如果车慢速行驶，则每km耗油1升花时间2mins；如果高速行驶，则每km耗油2升花时间一分钟。求能够在 t 内从0到达s的情况下的最小花费。

预处理+二重二分法+贪心

把所有的车根据花费为第一优先级升序以容量为第二优先级降序排列

然后预处理，使得，排在后面的车子的油箱容量必然大于等于前面的车子的容量，即把那些花费多但油箱容量小的车去掉。

扫完后排个序，然后每个val[i].c == INF，n--

预处理完后得到的车子的花费是单调不减的，油箱油量也是单调不减的。

然后对下标进行二分，l = 0， r = 新得到的n

在check函数来检查这个车是否能够满足条件，如果可以则返回true，继续向右二分。

在check内部，则是扫一遍加油站g[1...k+1]  //关于加油站要想排序，且把数据放在 g[1...k]，然后令g[0] = 0, g[k+1] = s;

然后对于每2个加油站之间，多长路程用高速，多长路程用低速，可以再用一个二分法获得，其中要求高速的路程尽可能长。

最后if(check(l)) cout << val[l].c << endl;
else if(check(r)) cout << val[r].c << endl;
else cout << -1 << endl;

即可

复杂度 O(nlognlogn)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 8;
const LL INF = 9e18;

struct p{
    LL c, v;
} val[maxn];

inline bool cmp(const p &a, const p &b)
{
    if(a.c != b.c) return a.c < b.c; else return a.v > b.v;
}

LL g[maxn], n, k, s, t;

inline bool incheck(const LL x, const LL &len, const LL &v)
{
    if(x * 2 + len - x <= v) return true;
    else return false;
}

inline bool check(const LL &x)
{
    LL l = 0, r = n, mid, tt = 0;
    for(int i = 1; i <= k + 1; i++){
        l = 0, r = g[i] - g[i-1];
        while(l + 1 < r){ mid = (l + r) >> 1;
            if(incheck(mid, g[i] - g[i-1], val[x].v)) l = mid;
            else r = mid;
        }
        if(incheck(r, g[i] - g[i-1], val[x].v)){
            tt += r;
            tt += (g[i] - g[i-1] - r) * 2;
        }
        else if(incheck(l, g[i] - g[i-1], val[x].v)){
            tt += l;
            tt += (g[i] - g[i-1] - l) * 2;
        }
        else{
            return false;
        }
    }

    if(tt <= t) return true; else return false; } int main() { #ifdef LOCAL freopen("c.txt", "r", stdin); //freopen("c.out", "w", stdout); int T = 2; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); cin >> n >> k >> s >> t;
    for(int i = 0; i < n; i++){ cin >> val[i].c >> val[i].v;
    }
    for(int i = 1; i <= k; i++){ cin >> g[i];
    }


    sort(val, val + n, cmp);
    //
    int c = val[0].c, v = val[0].v;
    for(int i = 1; i < n; i++){
        if(c <= val[i].c){ if(v > val[i].v){
                val[i].v = INF;
                val[i].c = INF;
            }
            else{
                c = val[i].c;
                v = val[i].v;
            }
        }
    }
    sort(val, val + n, cmp);
    for(int i = n - 1; i >= 0; i--){
        if(val[i].c == INF) n--;
        else break;
    }

    sort(g + 1, g + k + 1);
    g[k+1] = s;
    g[0] = 0;
    LL l = 0, r = n - 1, x;
    while(l + 1 < r){ x = (l + r) >> 1;
        if(check(x)) r = x;
        else l = x;
        //cout<<"here "<<x<<" "<<l<<" "<<r<<endl;
    }
    if(check(l)) cout << val[l].c << endl;
    else if(check(r)) cout << val[r].c << endl;
    else cout << -1 << endl;


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx