山頭狙撃戦二分の答え

質問C:山頭狙撃戦時間制限:1 Secメモリ制限:128 MB
テーマはLuckyが大部隊を援護するために、一騎打ちで敵と周旋し、その後敵に囲まれてある山の頂上にいる......など、なぜ狼牙山五壮士のように聞こえるのか!しかし焦らずに、今度はLuckyが十分な弾薬を持っていて、押し寄せてきた敵を一人一人殺すことができます.ラッキーは神銃手で、彼の銃の中に弾丸がある限り、彼は射程m(敵の位置から山までの直線距離で計算)以内の1人の敵を瞬時に射殺する.しかし射程内に敵がいなければ、弾丸節約とメンツの問題から、Luckyは敵が近づくのを待って射撃する.Luckyが自分の強さのために自ら膨張した時、彼は突然致命的なミスを発見した.彼が持っている銃は単発銃で、一発撃つたびに弾はすべてk秒の時間をかけて弾丸を入れなければならない.凶暴な敵はあなたが弾丸を交換するのを待つ時間がかかりません.彼らは常に1 m/sの速度で山に近づいている.敵が山に着いた時にラッキーが彼を殺すことができなければ、私たちのかわいそうなラッキーは敵の刺刀の下で犠牲になるだろう.今Luckyの心のインスピレーションはあなたに助けを求めるべきです:自分の命を守ってすべての敵を殲滅して、Luckyは最大でどのくらいの時間で銃に弾丸を積むことができますか?説明:最初からLuckyの銃に弾丸が1発あったと仮定し、装弾時間が確定すると、Luckyは常にこの時間で弾丸の積み下ろしを完了する.ラッキーが危険から抜け出すのを助けてほしい.
各組の入力データを入力し、最初の行には2つの整数nとmがあり、(2≦n≦100000;1≦m≦1000000)nは敵の数を表し、mはLuckyの射程を表す.次にn行があり、各行に1つの整数miがあり、(1≦mi≦1000000)、各敵が最初に山に対する距離(単位はメートル)を表す.
出力データのセットは、Luckyのバウンド時間(秒単位)を表す整数のみである.サンプル入力Copy 6 100 236 120 120 120 120 120サンプル出力Copy 25
人を二分しなくても簡単ではないと思います.のどのように毎回の速度を確定してしかも後ろの敵の距離によって絶えず速度を切り替えなければならなくて、このように前の時間に影響して、彼の換弾速度は一定なので、2点で答えを当てることができます.彼の交換速度を二分し、check関数のたびに敵をクリアできるかどうかをチェックします.主にcheck関数を言いますと、毎回の初めに弾丸が1発あるので、最初の敵は直接スキップすることができます.毎回vを加えるのはi番目の敵の換弾時間を消滅させ、換弾後に敵がLuckyの位置に着いたかどうかを検査します.早く着いたら要求に合わないに違いありません.まだ到着していない場合、射程範囲内にあります.交換したばかりの弾でそのまま撃てばOKで、次の敵を処理します.この時点で敵がまだ射程範囲内に入っていなければ、敵が射程に入る前に弾丸を交換し、現在の敵を直接スキップし(射程に入って直接消滅したため、最初の人と同じように処理)、時間をa[i]-mに更新することができる.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define X first
#define Y second
using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

const int N=100010,mod=1e9+7;

int n,m;
int a[N];
LL ans;

bool check(int v)
{
	int t=0;
	if(a[1]>m) t=a[1]-m;
	
	for(int i=2;i<=n;i++)
	{
		t+=v;
		if(a[i]<t) return false;
		if(a[i]-t>m)
			t=a[i]-m;
	}
	return true;
}

int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);

	scanf("%d%d",&n,&m);
	
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	
	sort(a+1,a+1+n);
	
	int l=0,r=1000000,mid;
	
	while(l<r)
	{
		mid=l+r+1>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}

	cout<<l<<endl;



	return 0;
}