一晚上就肝了一道题不写题解是不是有点亏？
其实是老师搞的二分练习题，挺有思维性的，故记之。
题意简单来说就是给你一堆车的油桶容量与价值的信息，问你在t时间内到达目的地的车中 价值最小那个是多少？
题目中给了两种行动方法，以下简称快走与慢走。显然由于每次到达加油站可以更新容量，整段路程可以根据加油站分成若干个子路程，对于每段子路程分别求出最小的t，最后累加即为一共需要的t了。
对于每个子路程，显然可以利用贪心的思想：只要我有油我就快走，除非我走了一段路程后，我预判出要是在快走我就没油啦，我就改成慢走，直到把油全耗完（特殊情况我们以后讨论）。那么应该怎么计算出这个路程长度呢？
我们设$x$为快走的路程，$y$为慢走路程，$V$为汽油总量，$s$为当前加油站与上一个加油站的距离，就可以得到以下的三个式子：
$$\begin{cases} 2x+y=V \ x+y=s \ x+2y=t\end{cases}$$
我们解一下前两个式子，可以得出：
$$\begin{cases} x=V-s \ y=2*s-V \end{cases}$$
将$x,y$代入即可求出对于这一子路程的$t$是多少了…
然后就可以毫无疑问的错了。
为啥会错？当然是$x,y$出现了负数解的情况啊！
我们进行简单的分类讨论：
- 如果$x<0$，你跑的比XG记者快还到不了，那你肯定就不可能到下一个点了，直接退了吧。。
- 如果$y<0$，说明你跑的太快，油桶没用完你就快走到了，那你此时的$t$加上$x$即可（对应花费的$x~min$）
- 除此之外均套用以上的式子算$t$
于是好像这一部分就没了？说着很复杂其实一想就出来了。。。
复杂度是$O(n)$的样子。
首先你$O(n)$一辆辆枚举肯定不行，超时。
其次的话看到最小值啥的想到二分应该是正常操作？然后你就又会发现给你的汽车价值根本就不存在单调性啥的，这二分啥啊。。
然后你就会自然的发现，这个价值是诈你的，真正决定能不能到达的是汽车的容量。所以你就直接二分容量，看最小满足条件的V是多少，搜一遍找一下满足$v[i]>V$且$min(w[i])$即可。
上我丑陋的代码，小细节都在代码里注释了：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
using namespace std;
//1. 判断在t内最小V的油桶多少-->二分+贪心？
//2. 看满足 <V的最小C是多少。
int n,s,k,t;
int c[MAXN],v[MAXN],d[MAXN];
bool check(int v)
{
long long sum=0;
for (int i=1;i<=k;i++)
{
int dis=d[i]-d[i-1];
long long x=v-dis,y=2*dis-v;
if (x<0) return 0;
if (y<0) sum+=dis;
else sum+=x+2*y;
// cout<<x<<" "<<y<<" "<<sum<<endl;
}
return (sum<=t);
}
int main()
{
scanf("%d%d%d%d",&n,&k,&s,&t);
for (int i=1;i<=n;i++) scanf("%d%d",&c[i],&v[i]);
for (int i=1;i<=k;i++) scanf("%d",&d[i]); d[++k]=s; //十年OI一场空，cin超时见祖宗
sort(d+1,d+k+1); //十年OI一场空，数组乱序见祖宗
long long l=0,mid=0,r=3000000000,ans=3000000000,V=3000000000;
while (l<r) //STEP:1
{
mid=(l+r)/2;
if (check(mid)) r=V=mid;
else l=mid+1;
}
for (int i=1;i<=n;i++) if (v[i]>=V) ans=min(ans,(long long)c[i]);
//STEP:2
if (ans==3000000000) printf("-1"); //十年OI一场空，忘记特判见祖宗
else printf("%lld\n",ans);
}