小行星

/*
	思路：求最少时间，看数据范围，显然选择nlgn 以内的算法解决，而因为随着时间的增加，机器人能扫的范围也会对应的增加
	故这题可以选择二分处理，二分时间，显然l=2,r=n*2。注意！题目要求：机器人最后得回到原位！！！ 
		关于l、r边界：因为k<n，考虑最好的情况：k=n-1，那么x=2便可以完成任务
									最坏：k=1，那么k需要向左跑一次、向右跑一次，自然是2*n
	确定好边界后，我们真正的问题是：如何O(n)判断时间x内，所有机器人能否扫完1-n区间 
	
	我们可以用贪心的思想，对所有机器人的位置排序使得:a1<a2<a3...<an，如果a1左边有地方需要扫描，我们肯定是选择让a1去扫描
	而不是a2、a3...,因为a1离他最近。因此，我们对每个ai，制定一个策略，用[p,n]表示需要扫描的区间
		1.如果p<ai，那么我们让ai去扫描[p,ai-1],因为要走回来，这个开销是（ai-p)*2。如果x连这个区间都扫不了
		，那么ai+1乃至以后肯定都扫不了这块区域，直接返回false。否则，我们假定ai已经走回原位，
		那么它需要尽可能向右贡献最大的价值，这个价值自然是a[i]+(x-(ai-p)*2)/2，于是p更新为这个价值+1
		 
		2. 如果p>=ai,那么我们让ai用掉所有的步数向右扫：x/2, p可能比这个值还大！（实际上最多等于）
		我们取p与a[i]+x/2+1之间的max即可 
	
	循环过程中只要p>n，那么返回true。注意p的定义！p=n时，代表[n,n]区间还需要扫描！ 
	
	分析结束，剩下是代码时间： （观察数据范围，以及大部分只使用+，故不需要开longlong）
*/
int n, m, a[100009];
bool check(int x){
	int p = 1;
	for(int i = 1; i <= m; i++){
		if(p < a[i]){
			int tot = (a[i] - p) * 2;
			if(x < tot) return false;
			p = a[i] + (x - tot) / 2 + 1;
		}else{
			p =  std::max(p, a[i] + x / 2 + 1);
		}
		
		if(p > n) return true;
	}
	return false;
}

int main(){
	std::cin >> n >> m;
	for(int i = 1; i <= m; i++){
		std::cin >> a[i];
	}
	if(n == m){
		std::cout << 0 << std::endl;
		return 0;
	}
	std::sort(a+1, a+m+1);
	int l = 1, r = n * 2, mid;
	while(l < r){
		mid = (r - l) / 2 + l;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}

std::cout << l << std::endl;
	return 0;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

小行星

TA的其他文章

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(2) （C++代码）

printf基础练习2 （C语言代码）

矩阵转置（C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

Hello, world! （C语言代码）

蓝桥杯2019年第十届省赛真题-扫地机器人(二分)

评论区

精彩推荐

简单的a+b （C语言代码）

简单的a+b （C++语言代码）

数组输出（C语言代码）--此题的题目描述有问题

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

简单的a+b （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

打印十字图（C语言代码）

1013题解

小行星

TA的其他文章

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(2) （C++代码）

printf基础练习2 （C语言代码）

矩阵转置 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

Hello, world! （C语言代码）

蓝桥杯2019年第十届省赛真题-扫地机器人(二分)

评论区

精彩推荐

简单的a+b （C语言代码）

简单的a+b （C++语言代码）

数组输出 （C语言代码）--此题的题目描述有问题

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

简单的a+b （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

打印十字图 （C语言代码）

1013题解

矩阵转置（C语言代码）

　　评论区

数组输出（C语言代码）--此题的题目描述有问题

打印十字图（C语言代码）