列表

详情

NC25545. 坐飞机

描述

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



输入描述

输入描述：先给出两个正整数 n 和 t，代表买了 n 张机票，所有飞机晚点时间和为 t。 
然后接下来 n 行，每行给出两个时间描述一个飞机的起飞和降落时间。 
  

输出描述

输出一行一个正整数表示答案

示例1

输入: 

3 2
1 2
2 3
3 4

输出: 

2

说明:

第一个航班和第二个航班均晚点一小时，则实际起飞和降落时间分别为[1,3]，[2,4],[3,4]. 则有两组弟弟配合。即第[1,2]个航班，和第[2,3]个航班

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 61ms, 内存消耗: 1516K, 提交时间: 2019-05-11 14:38:04 

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int m,n,cnt=0;
	cin>>m>>n;
	int a[m],b[m],c[m];
	for(int i=0;i<m;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
	}
	for(int i=0;i<m-1;i++)
	c[i]=a[i+1]-b[i];
	sort(c,c+m-1);
	for(int i=0;i<m-1;i++)
	{ if(n-c[i]-1>=0) 
	{
	n=n-c[i]-1;
		cnt++;
	}
	else
	break;
		
	}
	cout<<cnt;
	
}

C++11(clang++ 3.9) 解法, 执行用时: 125ms, 内存消耗: 864K, 提交时间: 2019-05-11 13:47:26 

#include <iostream>
#include <algorithm>
using namespace std;
int b[100000];
int n,t;
int s,e;
int main(){
	while(cin>>n>>t){
		cin>>s>>e;
		for(int i=2;i<=n;i++){
			cin>>s;
			b[i-2]=s-e;
			cin>>e; 
		}
		sort(b,b+n-1);
		int ans=0;
		for(int i=0;t>b[i]&&i<n-1;i++){
			ans++;
			t-=(b[i]+1);
		}
		cout<<ans<<endl;
	}
}

Python3 解法, 执行用时: 626ms, 内存消耗: 28152K, 提交时间: 2023-03-19 16:03:33 

n,t = map(int,input().split())
time = []
for i in range(n):
    time.append(list(map(int,input().split())))

surp = []
for i in range(n-1):
    surp.append(time[i+1][0]-time[i][1])

surp.sort()
i = 0
while i<len(surp):
    if t>=surp[i]+1:
        t=t-surp[i]-1
        i+=1
    else:
        break
        
print(i)

上一题

© 2024 nowcoder.com