wordpress 网站加速,网站建设 常用字体,雄安智能网站建设电话,技能训练企业网站建设可行性分析青蛙哥种了 n n n 棵竹子#xff0c;一开始第 i i i 棵竹子的高度为 h i h_i hi#xff0c;每天会长高 a i a_i ai。由于竹子长得太快#xff0c;青蛙哥不得不砍掉一些竹子#xff0c;但是#xff0c;每次只能砍下一截长度为 p p p 的竹子#xff0c;而且为了防…青蛙哥种了 n n n 棵竹子一开始第 i i i 棵竹子的高度为 h i h_i hi每天会长高 a i a_i ai。由于竹子长得太快青蛙哥不得不砍掉一些竹子但是每次只能砍下一截长度为 p p p 的竹子而且为了防止刀具磨损青蛙哥每天只能用刀砍 k k k 次。如果一个竹子的高度不足 p p p显然砍完之后高度不能为负数而应该是 0 0 0。
青蛙哥想知道他砍了 m m m 天之后最高的一棵竹子的最低高度是多少。每天先砍竹子砍完后竹子才会生长。 1 ≤ n ≤ 1 0 5 , m ≤ 5000 , k ≤ 10 , 0 ≤ p , h i , a i ≤ 1 0 9 1\le n\le10^5,m\le5000,k\le10,0\le p,h_i,a_i\le10^9 1≤n≤105,m≤5000,k≤10,0≤p,hi,ai≤109 首先二分答案 X X X判断 m m m 天之后是否所有竹子高度不超过 X X X。
由于砍的长度不一定为 p p p贪心不可行。考虑把全过程反过来看一开始竹子高度都不超过 X X X实际上就是等于 X X X每天竹子会缩短 a i a_i ai 长度如果长度为负就不合法然后你可以给竹子加 k k k 次长度 p p p。 m m m 天后竹子高度至少为 h i h_i hi。
现在贪心就好做了。首先每天的 k k k 次操作可以统筹分配分到其他天。前 m − 1 m-1 m−1 天如果有竹子在接下来一天会变成负数就给它加长度。到了第 m m m 天如果竹子高度小于 h i h_i hi也要加长度。
实现上可以用优先队列维护竹子在哪天需要加长度。到了第 i i i 天就处理优先队列队头的数据。
时间复杂度 O ( ( n m k ) log n log V ) O((nmk)\log n\log V) O((nmk)lognlogV) V V V 是值域。
#includebits/stdc.h
using namespace std;
#define ll long long
const int N1e51;
const ll INF1e18;
ll n,m,k,p,h[N],a[N],b[N],c[N];
ll la[N2],Max[N2],Maxnum[N2];
bool check(ll mid)
{priority_queuepairll,ll,vectorpairll,ll ,greaterpairll,ll q;for(int i1;in;i) b[i]mid;for(int i1;in;i) c[i]mid/a[i],q.push(make_pair(c[i],i));ll num0;for(int i1;im;i){numk;while(q.top().firsti){int idq.top().second;q.pop();if(!num) return 0;num--;b[id]p;c[id]b[id]/a[id];q.push(make_pair(c[id],id));}}numk;for(int i1;in;i){ll sumb[i]-a[i]*m;if(sumh[i]) num-(h[i]-sump-1)/p;}return num0;
}
int main()
{// freopen(bamboo.in,r,stdin);// freopen(bamboo.out,w,stdout);cin.tie(0)-sync_with_stdio(0);cinnmkp;ll l0,r2e15,ans;for(int i1;in;i) cinh[i]a[i],lmax(l,a[i]),rmax(r,a[i]*mh[i]);while(lr){ll midlr1;if(check(mid)) rmid-1,ansmid;else lmid1;}coutans;
}
