2 条题解
-
1
#include <bits/stdc++.h> using namespace std; const int N=100005; int n,m,k,s,t,C,a[N]; int check(int x){ int cnt=1,p=1; for (int i=2;i<=n;++i) if (a[i]-a[p]>=x) ++cnt,p=i; return cnt>=C; } int main() { cin>>n>>C; for (int i=1;i<=n;++i) cin>>a[i]; sort(a+1,a+1+n); int l=1,r=a[n]-a[1]; while (l<=r){ int mid=(l+r)/2; if (check(mid)) l=mid+1; else r=mid-1; } cout<<r; }
-
0
精简题意: 给出一个长度为n的序列,将c头牛安置进去,所有牛中相邻两头的最近距离越大越好。输出这个最大的最近距离。
“最小的最大”,是经典的二分题目;牛棚编号单调上升,具备二分的条件。因此,本题使用二分答案算法。
看输入样例,并不保证序列有序,因此需要排序:
sort(a+1,a+1+n);
经典的二分代码:
ll bf(){ ll l=0,mid,r=maxr; // maxr就是输入的序列中的最大值 while(l<=r){ mid=l+r>>1; // 使用位运算符计算mid if(check(mid)){ // 如果可以满足条件,那么更大! l=mid+1; }else{ r=mid-1; } } return r; // 返回r }
根据上面代码中的注释,可以想出check函数的功能是判断mid是否符合要求,如果符合则返回true,反之false
bool check(ll x){ // 检查参数x是否符合条件 ll ans=1,lp=1; // 第1个牛棚中肯定放置牛,所以牛数初始化为1;lp的意义是上一个有牛的牛棚的位置 for(ll i=1;i<=n;i++){ // 遍历每一个牛棚 if(a[i]-a[lp]>=x){ // 如果现在遍历到的牛棚与上一个有牛的牛棚之间相差的距离达到了参数x的要求 ans++,lp=i; // 那么牛数+1,并且更新lp } } return ans>=c; //如果x符合要求,那么返回true,反之false }
- 1
信息
- ID
- 653
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 5
- 标签
- 递交数
- 194
- 已通过
- 79
- 上传者