Description

公元20XX年，人類與外星人之間的大戰(zhàn)終于爆發(fā)。

現(xiàn)有一個(gè)人類軍團(tuán)，由n名士兵組成，第i個(gè)士兵的戰(zhàn)斗力值對(duì)應(yīng)一個(gè)非負(fù)整數(shù)ai (1 \leq i \leq n1≤i≤n)。

有一天，某個(gè)戰(zhàn)力爆表的外星人NaN單獨(dú)向地球人宣戰(zhàn)，已知它的戰(zhàn)力值為k (1 \leq k \leq 1e131≤k≤1e13)。現(xiàn)在該軍團(tuán)指揮官?zèng)Q定派遣編號(hào)在某個(gè)區(qū)間(l,r)內(nèi)的士兵去與敵方?jīng)Q斗。由于對(duì)手的不一般，現(xiàn)規(guī)定一個(gè)奇怪的戰(zhàn)力值計(jì)算公式：f(l,r)=[max(l,r)-min(l,r)]*(r-l+1)f(l,r)=[max(l,r)?min(l,r)]?(r?l+1)，(1 \leq l < r \leq n)(1≤l<r≤n)。

即只有當(dāng)f(l,r) \geq kf(l,r)≥k時(shí)才能戰(zhàn)勝敵人。請(qǐng)聰明的你來(lái)計(jì)算至少需要派出多少名士兵才能戰(zhàn)勝敵人。

Input

第一行輸入兩個(gè)整數(shù)nn，kk，(1 \leq n \leq 2e5,1 \leq k \leq 1e131≤n≤2e5,1≤k≤1e13),分別代表軍團(tuán)士兵個(gè)數(shù)和敵人戰(zhàn)力值；第二行輸入nn個(gè)整數(shù)，表示第i(1\leq i \leq n)i(1≤i≤n)名士兵的戰(zhàn)力值(0 \leq ai \leq 1e9)(0≤ai≤1e9)。

Output

答案輸出一個(gè)正整數(shù)表示應(yīng)派出士兵的數(shù)量，如果不存在則輸出-1?1。

輸出時(shí)每行末尾的多余空格，不影響答案正確性

樣例輸入復(fù)制

5 3 1 2 3 4 5

樣例輸出復(fù)制

3

?

解題報(bào)告：

? ? ? ?

AC代碼：

#include<bits/stdc++.h> #define ll long long using namespace std; const ll MAX = 2e5 + 5; int n; ll a[MAX],k; struct TREE {int l,r;ll val,maxx,minn; } tree[MAX * 4]; void pushup(int cur) {tree[cur].val = tree[cur*2].val + tree[cur*2+1].val;tree[cur].maxx = max(tree[cur*2].maxx , tree[cur*2+1].maxx);tree[cur].minn = min(tree[cur*2].minn , tree[cur*2+1].minn); } void build(int l,int r,int cur) {tree[cur].l=l;tree[cur].r=r;if(l == r) {tree[cur].val = tree[cur].maxx = tree[cur].minn = a[l];return ;}int m = (l+r)/2;build(l,m,cur*2);build(m+1,r,cur*2+1);pushup(cur); } ll querymax(int pl,int pr,int cur) {if(pl <= tree[cur].l && pr >= tree[cur].r) return tree[cur].maxx;ll res = 0;if(pl <= tree[cur*2].r) res = max(res,querymax(pl,pr,cur*2));if(pr >= tree[cur*2+1].l) res = max(res,querymax(pl,pr,cur*2+1));return res; } ll querymin(int pl,int pr,int cur) {if(pl <= tree[cur].l && pr >= tree[cur].r) return tree[cur].minn;ll res = LLONG_MAX;if(pl <= tree[cur*2].r) res = min(res,querymin(pl,pr,cur*2));if(pr >= tree[cur*2+1].l) res = min(res,querymin(pl,pr,cur*2+1));return res; } bool fit(int x) {for(int i = 1; i<=n-x+1; i++) {if((querymax(i,i+x-1,1) - querymin(i,i+x-1,1)) * x >= k) return 1;}return 0 ; }int main() {cin>>n>>k;for(int i = 1; i<=n; i++) cin>>a[i];build(1,n,1);int l = 0;int r = n;int mid = (l+r)/2;while(l<r) {mid = (l+r)/2;if(fit(mid)) r=mid;else l=mid+1;}printf("%d\n",l);return 0 ;}

?

總結(jié)

以上是生活随笔為你收集整理的jsk Star War （线段树维护区间最小最大值 + 二分）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。