Description
一条大河长L，n个石头，一只青蛙要过河。最多跳M次。问它的能力至少是多少，才能跳过去。
Algorithm
二分答案。这里是要求满足条件的最小的。
Code
#include <bits/stdc++.h>
using namespace std
;
const int N(500000+9);
int a
[N
], n
, m
;
int mid(int l
, int r
)
{
return l
+ (r
- l
) / 2;
}
int ok(int x
)
{
int l(0), cnt(1);
for (int i(1); i
<= n
+ 1; i
++) {
if (a
[i
] - a
[l
] <= x
) continue;
l
= i
- 1;
if (a
[i
] - a
[l
] > x
) return false;
cnt
++;
}
return cnt
<= m
;
}
int main()
{
ios
::sync_with_stdio(false);
int L
;
while (cin
>> L
>> n
>> m
) {
a
[0] = 0;
for (int i(1); i
<= n
; i
++)
cin
>> a
[i
];
sort(a
+ 1, a
+ n
+ 1);
a
[n
+ 1] = L
;
int l(0), r(L
), ans(0);
while (l
<= r
) {
int m(mid(l
, r
));
if (ok(m
)) r
= m
- 1, ans
= m
;
else l
= m
+ 1;
}
cout
<< ans
<< endl
;
}
}
阅读原文
转载请注明原文地址: https://www.6miu.com/read-83911.html
