pypy3(pypy3.6.1) 解法, 执行用时: 203ms, 内存消耗: 39988K, 提交时间: 2021-02-06 22:55:26

n, k = [int(x) for x in input().split()]
pos = sorted(int(x) for x in input().split())
l, r = 1, 1000000000000
ans = r

def check(itv: int) -> bool:
    cnt = 0
    for i in range(1, n):
        dis = pos[i] - pos[i - 1]
        cnt += dis // itv - (0 if dis % itv > 0 else 1)
    return cnt <= k

while l <= r:
    mid = l + r >> 1
    if check(mid):
        r = mid - 1
        ans = mid
    else:
        l = mid + 1
print(ans)

Python3(3.9) 解法, 执行用时: 1096ms, 内存消耗: 13840K, 提交时间: 2021-02-06 22:57:26

n, k = [int(x) for x in input().split()]
pos = sorted(int(x) for x in input().split())
l = 1
ans = r = 1000000000000

def check(itv: int) -> bool:
    cnt = 0
    for i in range(1, n):
        dis = pos[i] - pos[i - 1]
        cnt += dis // itv - (0 if dis % itv > 0 else 1)
    return cnt <= k

while l <= r:
    if check((mid := l + r >> 1)):
        r = (ans := mid) - 1
    else:
        l = mid + 1
print(ans)

C++(clang++11) 解法, 执行用时: 56ms, 内存消耗: 2060K, 提交时间: 2021-02-01 11:44:10

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[100010];
ll n,k,t;
int bs(ll l,ll r)
{
	ll mid=l+r>>1;
	if(l==r)
	return l;
	ll sum=0,i;
	for(i=1;i<n;i++)
	{
		sum+=(a[i]-a[i-1]-1)/mid;
	}
	if(sum>k)
	return bs(mid+1,r);
	return bs(l,mid); 
}
int main()
{
	int i,j;
	cin>>n>>k;
	for(i=0;i<n;i++)
	cin>>a[i];
	sort(a,a+n);
	cout<<bs(1,1e12); 
}