题解：P11181 [ROIR 2018 Day2] 书页

· · 题解

题解：

显而易见的贪心：

(1) 构造出的最后一张文本页作为这本书的最后一页。

(2) 使文本页尽可能多的同时让总页数尽可能少。

第 (1) 点很容易保证，因此我们主要考虑第 (2) 点该如何实现。

为了让文本页尽可能多，我们就应该保证文本页的页码都尽可能小，可以发现与此同时我们已经在让总页数尽可能少了（因为由 (1) 可得总页数取决于最后一张文本页的页码）。

我们一步一步解决这个问题：

（一）

我们不难想到，我们应当令第一张文本页的页码为 k + 1，随后不断地把前一张文本页的下一页安排为文本页。直到安排完这一文本页后，将下一页安排为文本页会使得这一页与之前所安排的所有文本页的页码之和超过题目所给定的 s 。但是此时我们发现按这样的方案构造，往往会余下一些页码没有安排，但是可以发现无论如何将这个页码分解为若干页码，所得到的页码都不能在之前找到对应的合法的页码（即未安排为文本页或插图页的页码），那这该怎么办？

（二）

这时我们只能让之前安排好的每一张文本页的页码都加上一，从而使我们的方案的文本页页码和增加，直到尽可能接近但不超过所给定的 s 。但是我们同样可以发现，这样同时增加页码有时候也不能使文本页的页码之和恰好与所给定的 s 相等，即遇到文本页的张数大于 s 与页码之和之差，且差不为零的情况。

（三）

我们可以只让其中一部分（从最后一张依次向前找）的文本页的页码加上一，刚好补足剩下的页码和之差，这下就万无一失了，我们完成了本题贪心的构造。

最后计算我们构造对答案的贡献：

首先令 ans = k ， 这是显而易见的一定要分配的插图页的张数。

随后，（一）的贡献显然为 0 ，因为文本页是连续安排的，所以其中不会有插图页。

而（二）的贡献在于每一次使全部的文本页页码加一都使得必须在第一张文本页前插入一张插图页才能让文本页的页码成立，我们记录下我们安排的文本页的张数 cnt，剩余的未安排的页数为 n，那么这对答案的贡献就是 \lfloor \frac{n}{cnt} \rfloor 。

对于（三）的贡献，我们知道当 cnt~ |~ n 时是不存在（三）的，而（三）一旦成立，那么对答案的贡献就一定是 1。

这里我们就已经完成了对整道题的分析，写代码就可以了。

另外，我这里使用比较好写的枚举，会不会超时呢？我们这里发现，我们枚举的页码是一个等差数列，我们知道等差数列的和是一个二次多项式，因此枚举的时间复杂度就是 O(n^{\frac{1}{2}}) ，完全可以通过题目中所给的 10^{12} 级别的数据，如果数据更加严格的话，可以写二分（虽然这时候很有可能已经要用高精了）。

AC Code :

#include<bits/stdc++.h>
using namespace std;
long long k, s, cnt;
int main() {
    cin >> k >> s;
    for (long long i = k + 1; s - i >= 0; ++i, ++cnt) {
        s -= i;
    }
    cout << bool(s % cnt) + k + s / cnt;
    return 0;
}