壹、关于题目 ¶
题目描述
\[\begin{aligned} \text{l ask of thee,art thou mankind？} \\ ——《ダンタリアンの書架》 \end{aligned} \]
作为「幻书」的管理者，妲丽安有一个封印着九十万六百六十六册「幻书」的迷宫书架，不过，在某一天，祂发现书架上的书因为某本「幻书」的失控而自发堆砌。祂当然能够处理这件事情，不过，作为一个喜欢奴役（？）自己的守钥人修伊，祂显然不是很想自己来收拾，于是，祂把这项任务交给了修伊。
迷宫书架中有从左到右 \(n\) 堆书，每堆书初始有 \(h_i\) 本书，即其高度初始为 \(h_i\)，由于「幻书」的影响，第 \(i\) 堆书在每个时刻结束会召集 \(a_i\) 本书叠在它们的上面。修伊每次可以搬走任意一堆书最上面的 \(p\) 本，当这一堆书不足 \(p\) 本，那么这一堆直接被搬空（但是魔力仍然存在，也就是说还是会有书本被召集叠在上面），即：如果这一堆书当前高度为 \(h\)，那么修伊搬一次之后的书本将变为 \(\max\{h-p,0\}\).
由于修伊为凡人之躯，他在一天只能搬 \(k\) 次书，为了让书架看上去尽可能整齐，他想让最高的一堆书高度最小，由于修伊仍然要被妲丽安折磨 \(m\) 天，他只能将计算 \(m\) 天后最大的书堆高度的最小值的任务委托给你。
数据范围
对于 \(100\%\) 的数据，满足 \(n\le 10^5,m\le 3\times 10^4,k\le 10,h_i,a_i,p_i\le 10^9\).
贰、关于题解 ¶
让最大高度最小，不难往二分方向思考。假设我们当前想要检查最终最大的最小高度为 \(H\) 的合法性。不过，检查这个高度是否合法好像还是很难？
搬运东西、移除东西，感觉好多就是反着考虑 —— 从终态开始，将各种操作倒着进行。比如，曾经的某道笛卡尔树的题，名字好像叫脚手架来着？那道题好像是从终态开始倒着拆。
于是这道题我们也可以采用相似的思路，从终态开始倒着来，先假定每堆书的高度都为 \(H\)，同时每天书堆的自动增加就变成了自动减少，修伊搬 \(p\) 本书就相当于增加 \(p\) 的高度。而我们需要保证任意时刻，每堆书的高度都大于等于 \(0\).
于是就有一个比较贪心的做法 —— 我们在某堆书马上就要变成负数的时候，给他加上 \(p\) 的高度，同时，某一天没有用完的增加高度操作可以叠加到后面的天去用。这个贪心显然正确。实现的时候开 \(m\) 个队列，维护当天需要给哪些书堆加上 \(p\) 本书即可。
时间复杂度 \(\mathcal O(m\log \max Height)\).
叁、参考代码 ¶
# include <bits/stdc++.h>
# include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
// # define USING_STDIN
# define NDEBUG
# define NCHECK
# include <cassert>
namespace Elaina {
# define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
# define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
# define fi first
# define se second
# define mp(a, b) make_pair(a, b)
# define Endl putchar('\n')
# define whole(v) ((v).begin()), ((v).end())
# ifdef NCHECK
# define iputs(Content) ((void)0)
# define iprintf(Content, argvs...) ((void)0)
# else
# define iputs(Content) fprintf(stderr, Content)
# define iprintf(Content, argvs...) fprintf(stderr, Content, argvs)
# endif
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
template <class T> inline T fab(T x) { return x < 0? -x: x; }
template <class T> inline void getmin(T& x, const T rhs) { x=min(x, rhs); }
template <class T> inline void getmax(T& x, const T rhs) { x=max(x, rhs); }
# ifndef USING_STDIN
inline char freaGET() {
# define BUFFERSIZE 5000
static char BUF[BUFFERSIZE], *p1=BUF, *p2=BUF;
return p1==p2 && (p2=(p1=BUF)+fread(BUF, 1, BUFFERSIZE, stdin), p1==p2)? EOF: *p1++;
# undef BUFFERSIZE
}
# define CHARGET freaGET()
# else
# define CHARGET getchar()
# endif
template <class T> inline T readret(T x) {
x=0; int f=0; char c;
while((c=CHARGET)<'0' || '9'<c) if(c=='-') f=1;
for(x=(c^48); '0'<=(c=CHARGET) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
return f? -x: x;
}
template <class T> inline void readin(T& x) { x=readret(T(1)); }
template <class T, class... Args> inline void readin(T& x, Args&... args){
readin(x), readin(args...);
}
template <class T> inline void writc(T x, char s='\n') {
static int fwri_sta[55], fwri_ed=0;
if(x<0) putchar('-'), x=-x;
do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
putchar(s);
}
} using namespace Elaina;
const int maxn=100000;
const int maxm=3e4;
int n, m, k;
ll h[maxn+5], a[maxn+5], p;
inline void input() {
readin(n, m, k, p);
rep(i, 1, n) readin(h[i], a[i]);
}
/** composition : < node, the times to be pulled up > */
typedef pair<int, int> Info;
queue<Info>Q[maxm+5];
inline bool check(ll H) { // lawks! long long!
ll sum=0;
rep(i, 1, n) sum+=(max(h[i]+1ll*a[i]*m-H, 0ll)+p-1)/p;
iprintf("sum == %lld\n", sum);
if(sum>m*k) return false;
iputs("the second stage\n");
rep(i, 1, m) while(!Q[i].empty()) Q[i].pop();
rep(i, 1, n) {
ll nxt=H/a[i]+1;
if(nxt<=m) Q[nxt].push({i, 0});
}
int residual=0, id, cnt;
rep(i, 1, m) {
if(int(Q[i].size())>residual) return false;
residual-=int(Q[i].size()), residual+=k;
while(!Q[i].empty()) {
auto cur=Q[i].front(); Q[i].pop();
id=cur.fi, cnt=cur.se+1; // add the pulling counter
ll nxt=(H+1ll*cnt*p)/a[id]+1;
if(nxt<=m) Q[nxt].push({i, cnt});
}
}
return true;
}
inline void work() {
ll l=0, r=ll(1e14), mid, ans=-1;
while(l<=r) {
mid=(l+r)>>1;
iprintf("Now l == %lld, r == %lld, mid == %lld\n", l, r, mid);
if(check(mid)) ans=mid, r=mid-1;
else l=mid+1;
}
writc(ans);
}
signed main() {
// freopen("bamboo.in", "r", stdin);
// freopen("bamboo.out", "w", stdout);
input();
work();
return 0;
}