[codeforces 729]C. Road to Cinema(前缀和 + 离线处理 + 二分)

发布于 2022-03-25  703 次阅读


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