题目链接:Problem - 729C - Codeforces
题目大意
现在俺在坐标为0的租车场要去一个电影院看电影,电影院在S点(一维数轴),电影T时刻开场。
我这里有很多车,每辆车有一个价格Ci和油箱容量Vi。
路上有K个加油站,每个加油站可以免费把油加满,车辆在起点时油箱是满的。
在路上有两种驾驶模式:
- 模式1:每1单位油走1公里,耗时2时间(正常模式)
- 模式2:每2单位油走1公里,耗时1时间(加速模式)
为了在T时刻前到达电影院,求需要花费的最小开销(也就是租车的钱)。
思路
一开始以为是Greedy(贪心),后面发现不对劲了,应该是二分。
首先将所有的道路都分离出来,每条道路有一个长度len[i],再将len数组排升序,找到所有“可以全程以模式2(加速模式)走的路段”和需要两种模式混合的路段。
这个通过二分可以直接找到分界点,如果一条道路恰好全部加速走,那么道路的长度应该为Vi / 2。
下图是本题的一些手写思路,借助前缀和可以快速地计算区间和。

发一波AC截图哈哈哈

代码
#include <bits/stdc++.h> #define pr printf #define sc scanf #define fi first #define se second #define pb push_back #define int long long using namespace std; typedef pair<int, int> PII; const int maxn = 2e5 + 10, inf = 1e10; int N, K, S, T; int sta[maxn], len[maxn], prefix[maxn]; vector<PII> vec; signed main() { cin >> N >> K >> S >> T; for(int i = 1;i <= N; ++ i) { //淦,因为用cin读入超时了两次 int c, v;sc("%lld %lld",&c, &v);//价格与容量 vec.pb({c, v});//离线处理 } for(int i = 1;i <= K; ++ i)sc("%lld",&sta[i]); sort(sta + 1,sta + 1 + K); //将S作为终点站加入,便于构造长度数组 sta[++ K] = S; for(int i = 1;i <= K; ++ i)len[i] = sta[i] - sta[i - 1]; //构造前缀和数组,以便于后续以O(1)复杂度求区间和 sort(len + 1, len + 1 + K); for(int i = 1;i <= K; ++ i)prefix[i] = prefix[i - 1] + len[i]; int ans = inf; for(auto i : vec) { int c = i.fi, v = i.se; if(v < len[K])continue;//如果没办法到终点就直接下一个 else //能到达终点,算一下最短时间 { //pos之前的都可以全部以加速模式通过,后面的一定以一定比例通过 int pos = lower_bound(len + 1,len + 1 + K, 1.0 * v / 2) - len; double t = 1.0 * prefix[pos - 1] + 3 * (S - prefix[pos - 1]) - v * (K - pos + 1); if(t <= 1.0 * T)ans = min(ans, c); } } pr("%lld\n",ans == inf ? -1 : ans); return 0; }
Comments NOTHING