A-坐飞机

佚名 7年前 (2019-05-12) 随笔 889人围观抢沙发百度已收录

链接：https://ac.nowcoder.com/acm/contest/892/A

题意：

鸡尾酒要去很多很多地方玩，于是他一次买了 n 张机票，初始鸡尾酒在第一个城市，对于任意的 i(1≤i≤n)i(1≤i≤n)，第 i 张机票可以从第 i 个城市飞到第 i+1 个城市。且起飞时间和降落时间分别为a_i，b_i。。为了在一班飞机到站后能赶上下一班飞机，鸡尾酒在买机票的时候保证对于任意的 i 和 i+1，有ai≤bi≤ai+1≤bi+1ai≤bi≤ai+1≤bi+1 但是由于不可抗力，某些飞机会晚点。如果对于某张机票 i(1≤i≤n)i(1≤i≤n),机票的实际降落时间c_i满足ci>ai+1ci>ai+1,鸡尾酒则会认为这是航班之间的一个弟弟配合。所有飞机的起飞降落的时间点均为整数。已知所有飞机总晚点时间之和为 t，求最多会有多少组航班之间的弟弟配合。对晚点的定义：假如某个飞机晚点时间为 x，则它的起飞时间不变，降落时间延后 x

思路：

贪心，取后一班航班起飞时间和上一班航班落地时间的差值，贪心排序即可。

代码：

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

typedef long long LL;

const int MAXN = 1e5+10;
int Up[MAXN], Down[MAXN];

int main()
{
    int n, t;
    cin >> n >> t;
    for (int i = 1;i <= n;i++)
        cin >> Up[i] >> Down[i];
    vector<int> time;
    for (int i = 2;i <= n;i++)
        time.push_back(Up[i]-Down[i-1]+1);
    sort(time.begin(), time.end());
    int res = 0;
    for (int i = 0;i < time.size();i++)
    {
        if (t >= time[i])
            res++, t -= time[i];
        else
            break;
    }
    cout << res << endl;

    return 0;
}

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。