CF1539C Stable Groups

CF传送门

本题大意就是给定一个数组$a[n]$，按照升序排列后，插入$k$个任意值的数，最后把相邻数差超过$x$的数分成两个不同的组，求最少划分为几个组。

思路：思维题
首先用$sort$把数组$a$排序，然后我们把$a[i+1]?a[i]>x$的两相邻项之差存入一个数组$c$，数组$c$长度记作$tot$显然，如果不插入$k$个数的话，$ans=tot+1$
接下来最关键的问题来了，如何插入$k$个数使得$a$的划分最少？
我们不妨从一个特例来看，假设$a[i+1]$为74$a[i]$为1，$x$为30，那么显然插入最少个任意数使$a[i+1]$与$a[i]$不划分的方法是：添加30,60，那么需要的数个数为73/30
那么对于一般的$need=c[i]/x$，整除的情况$need+1$，每减少一个划分，$ans?1$,$need?k$
$PS$：一定要开$longlong$！！！

啰嗦了这么多，代码很简短

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long ll;ll n,k,x,a[N],c[N];int main(){
    cin>>n>>k>>x;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+n+1);ll tot=0,ans=0;for(int i=1;i<n;i++)if(a[i+1]-a[i]>x) c[++tot]=a[i+1]-a[i];ans=tot+1;sort(c+1,c+1+tot);for(int i=1;i<=tot;i++){
    ll need=c[i]/x;if(c[i]%x==0) need-=1;if(need>k) break;else k-=need,ans-=1;}cout<<ans<<endl;return 0;
}