题目
题目描述 Mr. Kitayuta’s garden is planted with nn bamboos. (Bamboos are tall, fast-growing tropical plants with hollow stems.) At the moment, the height of the ii -th bamboo is h_{i}h i meters, and it grows a_{i}a i meters at the end of each day.
Actually, Mr. Kitayuta hates these bamboos. He once attempted to cut them down, but failed because their stems are too hard. Mr. Kitayuta have not given up, however. He has crafted Magical Hammer with his intelligence to drive them into the ground.
He can use Magical Hammer at most kk times during each day, due to his limited Magic Power. Each time he beat a bamboo with Magical Hammer, its height decreases by pp meters. If the height would become negative by this change, it will become 00 meters instead (it does not disappear). In other words, if a bamboo whose height is hh meters is beaten with Magical Hammer, its new height will be max(0,h-p)max(0,h?p) meters. It is possible to beat the same bamboo more than once in a day.
Mr. Kitayuta will fight the bamboos for mm days, starting today. His purpose is to minimize the height of the tallest bamboo after mm days (that is, mm iterations of “Mr. Kitayuta beats the bamboos and then they grow”). Find the lowest possible height of the tallest bamboo after mm days.
输入格式 The first line of the input contains four space-separated integers nn , mm , kk and pp ( 1<=n<=10{5},1<=m<=5000,1<=k<=10,1<=p<=10{9}1<=n<=10 5 ,1<=m<=5000,1<=k<=10,1<=p<=10 9 ). They represent the number of the bamboos in Mr. Kitayuta’s garden, the duration of Mr. Kitayuta’s fight in days, the maximum number of times that Mr. Kitayuta beat the bamboos during each day, and the power of Magic Hammer, respectively.
The following nn lines describe the properties of the bamboos. The ii -th of them ( 1<=i<=n1<=i<=n ) contains two space-separated integers h_{i}h i and a_{i}a i ( 0<=h_{i}<=10{9},1<=a_{i}<=10{9}0<=h i <=10 9 ,1<=a i <=10 9 ), denoting the initial height and the growth rate of the ii -th bamboo, respectively.
输出格式 Print the lowest possible height of the tallest bamboo after mm days.
题意翻译 给定 nn 个数 h_{1 \dots n}h 1…n 。 你需要进行 mm 每轮操作为轮操作 kk 每次修改都可以选择一个数字 h_ih i 修改为 \max(h_i - p, 0)max(h i ?p,0)。 每轮操作后每个 h_ih i 将被修改为 h_i a_ih i a i 。 你需要最小化最终 h_{1 \dots n}h 1…n 最大值。 n \le 10^5n≤10 5 ，m \le 5 \times 10^3m≤5×10 3 ，k \le 10k≤10。 输入输出样例 输入 #1复制 3 1 2 5 10 10 10 10 15 2 输出 #1复制 17 输入 #2复制 2 10 10 1000000000 0 10 0 10 输出 #2复制 10 输入 #3复制 5 3 3 10 9 5 9 2 4 7 9 10 3 8 输出 #3复制 14
思路
假设第m天后竹子自然生长的最高高度是max_height。那么我们经过处理后的答案一定会在区间[0,max]内部。不可能超过我们最高的竹子。
这时，我们假设最后一个答案ans，然后找到正确的答案。
如果答案是正确的，所有的竹子在第m天的高度都会小于或等于ans。前一天竹子的最高高度是ans-a[i] p*times，times这是我们处理竹子的次数。然后前一天类比。我们反向处理竹子。
无论我们如何处理竹子的最终高度，它会大于我们预期的答案ans，这意味着我们的答案很小，继续在范围内(ans,max]寻找。相反，在[0，ans]寻找。
代码
#include<bits/stdc .h> using namespace std; #define int long long int n,m,k,p; const int maxn = 1e5 5; int a[maxn],h[maxn]; int he[maxn]; struct bamboo {
int ne; int id; bool operator < (const bamboo & x) const {
return x.ne < ne; }//重载运算符 } bam[maxn]; bool check(int x) {
priority_queue <bamboo> q; // memset(he,x,sizeof(he)); for(int i = 1; i<= n; i++) he[i] = x;//初始值 for(int i = 1; i <= n; i++) if(he[i] - a[i] * m < h[i]) q.push({
x / a[i],i});//预处理 for(int i = 1; i <= m; i++)//枚举m天 for(int j = 1; j <= k; j++) {
//增加k棵竹子高度 if(!q.size()) return 1; bamboo y = q.top(); q.pop(); if(y.ne < i)//无论如何都不满足 return 0; he[y.id] += p; if(he[y.id] - a[y.id] * m < h[y.id])//增加后仍不满足就进堆 q.push({
he[y.id] / a[y.id],y.id}); } return q.empty(); } signed main() {
scanf("%d%d%d%d",&n,&m,&k,&p); for(int i = 1; i <= n; i++) scanf("%d%d",&h[i],&a[i]); int l = 0,r = 0; for(int i = 1; i <= n; i++) r = max(r,(h[i] + a[i] * m))： while(l < r) {
int mid = l + r >> 1; if(check(mid)) r = mid; else l = mid +1; } cout << l << endl; return 0; }