南华网站建设,网站怎样优化关键词好,ui网站开发,中国建材网官方网站Description
公元20XX年#xff0c;人类与外星人之间的大战终于爆发。
现有一个人类军团#xff0c;由n名士兵组成#xff0c;第i个士兵的战斗力值对应一个非负整数ai (1 \leq i \leq n1≤i≤n)。
有一天#xff0c;某个战力爆表的外星人NaN单独向地球人宣战#xff0c…Description
公元20XX年人类与外星人之间的大战终于爆发。
现有一个人类军团由n名士兵组成第i个士兵的战斗力值对应一个非负整数ai (1 \leq i \leq n1≤i≤n)。
有一天某个战力爆表的外星人NaN单独向地球人宣战已知它的战力值为k (1 \leq k \leq 1e131≤k≤1e13)。现在该军团指挥官决定派遣编号在某个区间(l,r)内的士兵去与敌方决斗。由于对手的不一般现规定一个奇怪的战力值计算公式f(l,r)[max(l,r)-min(l,r)]*(r-l1)f(l,r)[max(l,r)−min(l,r)]∗(r−l1)(1 \leq l r \leq n)(1≤lr≤n)。
即只有当f(l,r) \geq kf(l,r)≥k时才能战胜敌人。请聪明的你来计算至少需要派出多少名士兵才能战胜敌人。
Input
第一行输入两个整数nnkk(1 \leq n \leq 2e5,1 \leq k \leq 1e131≤n≤2e5,1≤k≤1e13),分别代表军团士兵个数和敌人战力值第二行输入nn个整数表示第i(1\leq i \leq n)i(1≤i≤n)名士兵的战力值(0 \leq ai \leq 1e9)(0≤ai≤1e9)。
Output
答案输出一个正整数表示应派出士兵的数量如果不存在则输出-1−1。
输出时每行末尾的多余空格不影响答案正确性
样例输入复制
5 3
1 2 3 4 5
样例输出复制
3 解题报告 AC代码
#includebits/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*21].val;tree[cur].maxx max(tree[cur*2].maxx , tree[cur*21].maxx);tree[cur].minn min(tree[cur*2].minn , tree[cur*21].minn);
}
void build(int l,int r,int cur) {tree[cur].ll;tree[cur].rr;if(l r) {tree[cur].val tree[cur].maxx tree[cur].minn a[l];return ;}int m (lr)/2;build(l,m,cur*2);build(m1,r,cur*21);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*21].l) res max(res,querymax(pl,pr,cur*21));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*21].l) res min(res,querymin(pl,pr,cur*21));return res;
}
bool fit(int x) {for(int i 1; in-x1; i) {if((querymax(i,ix-1,1) - querymin(i,ix-1,1)) * x k) return 1;}return 0 ;
}int main()
{cinnk;for(int i 1; in; i) cina[i];build(1,n,1);int l 0;int r n;int mid (lr)/2;while(lr) {mid (lr)/2;if(fit(mid)) rmid;else lmid1;}printf(%d\n,l);return 0 ;}
