贪心

假设当前位于第i个加油站，后面有比i费用低的加油站j：

• j在行驶范围内，那就加油量刚好到j就可以，去j再加油。
• j不在行驶范围内，那就加满油，去后面寻找比它费用低的

code

#include <bits/stdc++.h>
using namespace std;
#define ll long long

namespace syr
{
	const ll N = 5e4+10;
	struct node {
		ll d; //距离
		ll p; //价格
	}a[N];
	ll n, c, s, L, ans;
	ll l[N];
	deque <ll> q;
	bool cmp (node a, node b) {
		return a.d<b.d;
	}
	void work()
	{
		cin>>n>>c>>s>>L;
		for (ll i=1; i<=n; i++)
			cin>>a[i].d>>a[i].p;
		a[n+1] = {L, 1000000000};
		n++;
		sort(a+1, a+1+n, cmp);
		for (ll i=1; i<n; i++) {
			if (a[i+1].d-a[i].d>c) {
				cout<<-1<<'\n';
				return;
			}
		}
		for (ll i=n; i>=1; i--) {
			while (!q.empty() && a[q.front()].d-c>a[i].d) q.pop_front();
			while (!q.empty() && a[q.back()].p>a[i].p) q.pop_back();
			if (!q.empty()) l[i] = q.back();
			else l[i] = i;
			q.push_back(i);
		}
		if (s<a[1].d) {
			cout<<-1<<'\n';
			return;
		}
		s -= a[1].d;
		for (ll i=1; i<=n; ) {
			if (i==l[i]) {
				if (a[n].d-a[i].d<=c) {
					ll t = max((ll)0, a[n].d-a[i].d-s);
					cout<<ans+t*a[i].p<<'\n';
					return;
				}
				ans += (c-s)*a[i].p;
				s = c-(a[i+1].d-a[i].d);
				i++;
			}else {
				ll dis = a[l[i]].d-a[i].d;
				if (s>=dis) {
					s -= dis;
					i = l[i];
					continue;
				}
				ans += (dis-s)*a[i].p;
				s = 0;
				i = l[i];
			}
		}
	}
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	syr::work();
	return 0;
}

完结散花~~

首先我们想到贪心

首先按照距离起点的长度排序

对于我们到达每一个加油站

我们看如果当前加油站后面如果有比当前加油站价格还小的，那我们就去那里，只用加能到达那里的油就可以

如果我们的油到不了比当前最小的，那我们就加满油，去到我们能去到的最小的

非常难泵

写了一个很唐氏的分治。。。。

我们沿用上次模拟赛的打游戏，考虑分治。

我们先去找区间上最便宜的油站，然后我们写一个$solve(l,r,S)$，表示初始油量为 $S$ ,从油站 $l$ 到油站 $r+1$ 时油量最少剩下多少，因为最少剩下和花费最少一定同时满足，特别的，我们不妨令 $d_{n+1}=L$

所以我们要去递归得做 $solve(l,r,S)$ ，同时记录一个花费就好了。

我们写一个 $ST$ 表去查找区间上最便宜的油站，然后先去递归跑 $solve(l,mnid-1,S)$，这样我们得到了跑到 $mnid$ 的油量，然后我们尽可能多的去在这个站点上加油，当然尽可能多是指如果后面跑不满就加满油，否则用多少加多少。

考场上因为 $-1$ 看做了导致的

SOLUTION

自己敲代码吧，，