#CF 1700d.River Locks 题解(思维、递推、dp)

原题链接.

有n个水池，水池的容量是一个数组v[n]。现考虑选定其中m个水池，每个水池插根管子以每秒1单位的速度注水。注意这些水池的高度是按下标顺序递减的，即如果前一个水池的水满了，之后注入的水会流到后面还没满的水池。
现在给你q个询问，每个询问给一个时间，问你能否在该时间内把所有水池注满，如果可以，应给出所用管子的最小值。

法一：（我的方法）
发现随着用时的增加，所用的最小管子数是单调不增的。
那么给你一个用时t，怎么算出所用最小管子数minp呢？首先发现,minp>= ⌈ ( ∑ k = 1 n v k ) / t ⌉ displaystyle left⌈(sum_{k=1}^n v_k )/t right ⌉ ⌈(k=1∑n​vk​)/t⌉. 我在想，能直接用目标数组所有元素之和 ⌈ ( ∑ k = 1 n v k ) / t ⌉ displaystyle left⌈(sum_{k=1}^n v_k )/t right ⌉ ⌈(k=1∑n​vk​)/t⌉来作为答案吗？
这是不行的，因为有可能有浪费，导致填不满（这里的浪费指后面的池子的水流到river里的情况）。如下面的例子：

考虑t=3,v[ ]={5,1}, ⌈(5+1)/3⌉=2<=管子数n，但仍不行，因为3秒内填不满容量为5的池子，而第二个池子多出来的水全部浪费掉了。
再举个更复杂点的例子： t=5,v[]={5,7,7,1}. ⌈(5+7+7+1)/5⌉=4<=管子数n，但也不行，因为⌈(5+7+7)/3⌉=4>3, 即长度为3的前缀填不满。

通过这些例子的模拟我发现，v数组的每一个前缀⌈prefix[i]/i⌉都<=t，等价于整体能在t内填满。所以说我们算出填满v的每一个前缀的最短用时的最大tmax(根据之前的分析，tmax应该等于为每个水池分配一个管子，所用的时间。)，如果说t

下面简单证明一下加粗的结论：
一 充分性
数学归纳法，从前往后推。
1：前缀 ⌈ p r e f i x [ 1 ] / ( 1 ) ⌉ ⌈prefix[1]/(1)⌉ ⌈prefix[1]/(1)⌉<=t，说明长度为1的前缀会被填满
2：i>=2.若长度为i-1的前缀被填满，多出来的水流到池子i,等价于i个池子共享i根管子流出来的水，又因为 ⌈ p r e f i x [ i ] / i ⌉ < = t ⌈prefix[i]/i⌉<=t ⌈prefix[i]/i⌉<=t,所以长度为i的前缀会被填满。

二 必要性
还用归纳法，万金油！
1:i>=2.如果长度为i的前缀被填满了，说明长度为i-1的前缀被填满了，故多出来的水流到池子i,等价于i个池子共享i根管子流出来的水，所以 ⌈ p r e f i x [ i ] / i ⌉ < = t ⌈prefix[i]/i⌉<=t ⌈prefix[i]/i⌉<=t
2:如果长度为1的前缀被填满，说明 ⌈ p r e f i x [ 1 ] / 1 ⌉ < = t ⌈prefix[1]/1⌉<=t ⌈prefix[1]/1⌉<=t

法二：（官方题解方法）
用dp做。
大概的意思是：如果管子数为k一定，那么给前k个池子分配管子是最优解。用dp[i]表示i根管子填满所有池子所需最短时间。dp[i]一定单调不增，这样一来，给出一个t，可以用二分找到对应的最小管子数i，如果跃出边界，说明无解。

方法一

#include 
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef pair PII;
typedef long long LL;
const int Mod=1e9+7,N=2e5+10;
 
 
template  bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template  bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template  void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}
 
LL sum=0;
int main()
{
    int n,maxn=1,q;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        sum+=x;
        maxn=max((sum+i-1)/(LL)i,(LL)maxn);
 
    }
    cin>>q;
    while(q--)
    {
        int x;
        cin>>x;
        if(x 
方法二
 
请参考官方题解
 
4.收获 
此题的本质在于管子流出来的水未必能被各个池子所共享（靠后的池子溢出，就会浪费）。