题目链接：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;
}