题目简介

这道题给我们n两汽车，每辆汽车有所需要的价钱c与其油箱的最大存油量v，然后给我们一段路程s，其中有k个加油站，问是否能在t时间内跑完这段路程。所有汽车均有两种运行模式：
1.普通模式：1km 用 2min 用 1L 油。
2.加速模式：1km 用 1min 用 2L 油。
如果能跑完则输出最少需要花费的租车费。
如果全都没办法跑完全程则输出-1。
（二分+贪心）

样例输入

3 1 8 10
10 8
5 7
11 9
3

样例输出

10

解题思路

1.用结构体储存汽车数据，并将汽车数据按照油箱大小从小到大排序。
2.计算每段加油站之间的距离。（ps ： 加油站的位置不一定是顺序给出的 ， 需要排序）
3.首先判断油箱最大的汽车是否能在规定时间内跑到终点，若不能直接输出-1。
4.若油箱最大的汽车能跑完全程则用二分法找出能跑完全程的最小油箱量。然后再在最小油箱量和最大油箱的汽车数据之间选出需要花费钱最小的那一个。

关于如何判断是否满足条件：
本题只有三种情况。（按照每一段距离来计算时间，记油箱容量为x，若时间小于规定时间则成立）
1.distance > x ，则中途没油。
2.distance * 2 <= x ， time += distance 。在这段距离内能全速跑。
3.distance < x < distance2 ， time += (3distance - x) 。 尽量加速跑。

数据较大，最好用long long。
（ps : 因为我比较菜所以几乎所有东西都改成了long long ）

代码如下

#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 200050;

LL con = 0;      // 计算有多少段距离；
LL sta[maxn];     // 开一个加油站位置的数组；
LL dis[maxn];     // 每两个加油站之间距离的数组；
LL  n,k,s,t;      // n代表汽车数量，k代表加油站数量，s为路程，t为最大时间；
struct car
{
    LL c,v;      // 包含车子的数据,c为价钱,v为最大油量；
} cars[maxn];

bool cmp(car a,car b)       // 让车子数据按照油量从小到大进行排序；
{
    if(a.v != b.v) return a.v < b.v;
}

bool judge(LL x)
{
    LL time = 0;

    for(int i = 0 ; i < con ; i++)
    {
        if(dis[i] > x) return false ;// 若距长于最大油量则不可能通过；
        if(2*dis[i] <= x) time += dis[i];
        else time += (3*dis[i] - x);
    }
    if(time > t) return false;
    return true;
}

int main()
{
    scanf("%lld%lld%lld%lld",&n,&k,&s,&t);
    for(int i = 1 ; i <= n ; i++)                // 从1到n读取汽车的数据；
        scanf("%lld%lld",&cars[i].c,&cars[i].v);
    sta[0]=0;
    for(int i = 1 ; i <= k ; i++)          // 从1到n读取加油站的位置；
        scanf("%lld",&sta[i]);
    sta[k+1]=s;
    sort(sta,sta+k+1);  // 将加油站的位置按从小到大排序；
    for(int i = 1 ; i <= k+1 ; i++)   // 储存每段距离；
    {
        dis[con]=sta[i]-sta[i-1];
        con++;
    }
    sort(cars+1,cars+1+n,cmp);  // 讲1到n号车按油量从小到大排序；
    if(!judge(cars[n].v)) printf("-1\n");  //若最大油量不可能跑到终点则输出-1；
    else                                 // 二分查找满足条件的最小油量；
    {
        LL l = 1;
        LL r = n;
        LL goal = n;
        while(l <= r)
        {
            LL mid = (l + r)/2;
            if(judge(cars[mid].v))
            {
                r = mid - 1;
                goal = mid;
            }
            else l = mid + 1;
        }

        LL minn = 1000000005;
        for(int i = goal ; i <= n ; i++)
        {
            if(cars[i].c <= minn) minn = cars[i].c;
        }
        printf("%lld\n",minn);
    }

}