引出下文

题目背景

在一场精彩纷呈的真人秀节目里，勇敢的小核桃正在惊险的吊桥上迎接极限挑战！

这座吊桥高悬于可怕的深渊之上，由铁索和木板搭建而成，而每一块木板上都放置着一枚诱人的金币作为奖励！

题目描述

游戏拉开帷幕，小核桃起始于 1 号木板。木板之间存在一定间距，并且向右无限延展。小核桃需要在木板之间奋力跳跃来移动，稍有不慎便会坠入深渊！

每块木板上的金币都十分便于携带，可以认为取走一个木板上金币的时间几乎可以忽略不计。

然而，不幸的是，这座吊桥上有 n 块木板较为脆弱。第 i 号脆弱木板将会在被经过的 t_i 秒后碎裂！所以小核桃在进入 d_i 号木板后的 t_i 秒及以后便不能再回到该木板上了，他必须在 t_i 秒前回到前面的木板上。

经过 1e18 米跑步锻炼的小核桃，身手异常敏捷，他在相邻两个木板之间跳跃的时间可以视为 1 秒。

小核桃渴望获取尽可能多的奖品，并且要安全地回到 1 号木板以返回地面。您能告诉他，他最远能够抵达哪块木板吗？

输入格式

第一行是一个正整数 n ，代表脆弱木板的数量。

接下来的 n 行，第 i 行有两个正整数 d_i 和 t_i ，分别表示第 i 个脆弱木板的编号和碎裂时间。

输出格式

输出一行一个正整数，表示小核桃最远能到达的木板编号。

示例输入 1

CPP

1
2 2

示例输出 1

CPP

示例输入 2

CPP

示例输出 2

CPP

提示

样例解释 #1

倘若仅前往 2 号木板，您将在 1 秒时进入 2 号木板，2 秒时返回 1 号木板，能够安全返回。

倘若前往 3 号木板，您将在 1 秒时进入 2 号木板，2 秒时进入 3 号木板。然而此时再返回 2 号木板至少需要 2 秒，此时 2 号木板已经碎裂，无法返回 1 号木板。

样例解释 #2

若前往 9 号木板，则返回 5 号木板时，耗费了 8 秒，此时木板已经碎裂。所以最远只能到达 8 号木板，返回 5 号木板时仅用了 6 秒，能够安全返回。

数据范围与约定

对于 30% 的数据，确保 1 ≤ n ≤ 100 。

对于 100% 的数据，确保 1 ≤ n ≤ 10^6 ，1 ≤ d_i, t_i ≤ 10^18 ，且 d_i 互不相同。代码：

CPP

#include <bits/stdc++.h>
using namespace std;
struct node{
	int num,t;
}a[1000010];
bool cmp(node a,node b){
	return a.num<b.num;
}
int n,minn=1e9,ans=1;
int main() {
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].num>>a[i].t;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		if(minn/2+ans-1<a[i].num){
			break;
		}
		minn=min(a[i].t,minn);
		ans=i;
	}
	cout<<minn/2+a[ans].num-1;
    return 0;
}

下文

讨论操作

回复

相关推荐

引出下文