[CF505E]Mr. Kitayuta vs. Bamboos & Dantalian's

壹、关于题目 ¶

题目描述

\[\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;
}
上一篇:NOIP模拟56


下一篇:C++内联inline