【SSL_2020.10.27】小biu放牛

本文主要是介绍【SSL_2020.10.27】小biu放牛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

小biu放牛

---

解题思路

这道题呢，我们试着用二分来处理绳子的长度，然后用一个函数来处理这个长度的可行性。我们用贪心的方法，将每头牛尽量往前放，以保证后面牛的位置最大，当mid到的绳子的长度不能满足牛的排列时，我们就退出。当然，如果牛被挤出边界了，那么自然也不行。

code

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;ll n,x,m;
ll a[50010];ll abs(ll t)
{if(t<0)return -t;return t;
}ll check(int mid)
{ll hd,tl;hd=tl=0;for(int i=1;i<=n;i++){hd=max(tl,a[i]-mid-x);if(abs(hd-a[i]+x)>mid)return 0;tl=hd+2*x;if(tl>m)return 0;}return 1;
}int main()
{cin>>n>>x>>m;if(n*x*2>m){cout<<-1<<endl;return 0;}for(int i=1;i<=n;i++)scanf("%d",&a[i]);int l=0,r=m;while(l<=r){int mid=(r+l)/2;if(check(mid))r=mid-1;elsel=mid+1;}cout<<l<<endl;
}

这篇关于【SSL_2020.10.27】小biu放牛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---