P2678 跳石头

类似：P3853 [TJOI2007]路标设置

题目背景

一年一度的“跳石头”比赛又要开始了!

题目描述

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。

输入格式

第一行包含三个整数 L,N,M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 L≥1 且 N≥M≥0。

接下来 N 行，每行一个整数，第 ii 行的整数 D_i( 0 < D_i < L)， 表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出格式

一个整数，即最短跳跃距离的最大值。

输入输出样例

输入 #1

1
2
3
4
5
6
25 5 2 
2
11
14
17 
21

输出 #1

1
4

二分答案…

注意是起点和终点之间有 N 个石头，并且终点不能移走

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const int MAX=50000+10;
int L,n,m,ans,a[MAX];
bool isok(int x){
	int last=0,cnt=0;
	fi(i,0,n){
		if(a[i]-last<x) {
			cnt ++;
		}else last = a[i];
		if(cnt>m) return false;
	}
	if(a[n]-last<x) return false;//终点不能移走 
	return true;
}
int main(){
	freopen("in","r",stdin);
	sf(L);sf(n);sf(m);
	int last=0;
	fi(i,0,n)
		sf(a[i]);
	a[n] = L;
	int l=0,r=L;
	while(l<=r){
		int m=(l+r)/2;
		if(isok(m)){
			ans = m;
			l=m+1;
		}
		else r=m-1;
	}
	pf(ans);
	return 0;
}

P3743 kotori的设备

题目描述

kotori 有 n 个可同时使用的设备。第 i 个设备每秒消耗ai个单位能量。能量的使用是连续的，也就是说能量不是某时刻突然消耗的，而是匀速消耗。也就是说，对于任意实数 ,在 k 秒内消耗的能量均为k*ai 单位。在开始的时候第 i 个设备里存储着bi个单位能量。

同时 kotori 又有一个可以给任意一个设备充电的充电宝，每秒可以给接通的设备充能 p 个单位，充能也是连续的，不再赘述。你可以在任意时间给任意一个设备充能，从一个设备切换到另一个设备的时间忽略不计。

kotori 想把这些设备一起使用，直到其中有设备能量降为 0。所以 kotori 想知道，

在充电器的作用下，她最多能将这些设备一起使用多久。

充电宝可以瞬间换一个设备充电，比如，当期望时间为 x , 当有2个设备同时快要到 0 时，选择哪一个先充？ 方法是先把其中一个充到 x ,再充另一个。因为充电宝可以瞬间移动，所以效果是一样的（不看题解完全想不到…）

然后，就是普通的二分了。

代码略