题解：CF730F Ber Patio

liujiaxi123456 · 2025-06-30 14:48:47 · 题解

给一篇 O(n + \sum a) 的正解。

思路：

这个数据范围确实比较奇怪，首先可以考虑 DP。

但是 DP 是 O(\frac{nb}{k}) ，其中 k=10，考虑是否有更优秀的做法。

我们考虑加入贪心的思想，先想的是从左到右贪，但是发现后效性太过复杂。

于是考虑从右往左贪：

• 我们考虑先合法，再最优。假设每天都不使用积分。

• 则我们可以得到在这个情况下每天能用的积分 have_i = \frac{a_{i-1}}{10} 。

• 我们的思路是让从后往前的每一天都尽可能花到上限 \frac{a_i}2 。

• 由于积分什么时候花的价值一样，所以这样贪到最后一定是对的。

• 这样我们可以得到一个很好的性质：

  • 所以不用处理剩余积分的贡献。

• 如果不太理解可以看具体流程。

考虑具体流程：

• 首先我们有 need = \frac {a_i}2 ，表示 i 天需要的积分。

• 容易发现，need 的零头由于不可能带来新的积分，所以什么时候花都一样，我们将它加入 free 的积分里。

• 由于我们要尝试花到上限，则 i+1 天的积分必然减少：

  • 我们先使用 i+1 剩余的积分 have_{i+1} 。

  • 当 i+1 的积分不够时，i 需要去前面借 10 个积分。

• 我们现在尝试用掉 have_i：

  • 先把 free 里的积分用完。

  • 如果 have_i 还有，尝试把后面欠下的债还了。

  • 注意，每个积分只能还一笔小于等于 10 且债主相同的债。

  • 不能把债主不同的两笔债拼在一起一次换。

  • 相当于一笔 x 的 4 积分，和 y 的 5 积分，要用两个积分，而不是 4+5\le10 用一个积分。

• 具体的见代码。

Code：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int Maxn = 5005;

namespace Josh_zmf {

    int N, sum, have[Maxn], a[Maxn], ans[Maxn];
    vector <int> Free, lent[11];

    inline int main() {
        cin>> N>> have[1];
        for(int i=1; i<=N; i++) cin>> a[i], sum += a[i], have[i+1] = a[i]/10; // 先假设不用积分，i+1 天可以得到 a[i]/10 的积分
        for(int i=N; i; i--) {
            int need = a[i]/2;
            // 处理今天支付的零头
            int free = min(a[i]%10, need); // 用了也没有积分，就没必要今天用了，随便哪天用都行
            need -= free, Free.insert(Free.end(), free, i);
            // 处理今天使用积分造成 i+1 缺乏积分的影响
            for(int x=need/10; x; x--) {
                if(have[i+1])   have[i+1]--, Free.insert(Free.end(), 10, i); // 原来 i 支付带来的积分 i+1 没有用完，i 可以多用 10 个积分而没有影响
                else    lent[10].push_back(i); // 用完了，所以 i 需要去前面借 10 个积分
            }
            need %= 10;
            if(need) {
                if(have[i+1])   have[i+1]--, Free.insert(Free.end(), need, i); // 没有用完，i 可以多用 need 个积分而没有影响
                else    lent[need].push_back(i); // 用完了，所以 i 需要去前面借 need 个积分
            }
            // 尝试把 i-1 不用积分带来的积分用掉
            while(have[i] and !Free.empty())    have[i]--, ans[Free.back()]++, Free.pop_back(); // 先用零钱
            for(int x=10; x; x--) {
                while(have[i] and !lent[x].empty()) {
                    have[i]--; // 相当于把这个积分转到 have[lent[x].back()+1] 那里，这样 lent[x].back() 就可以多用一轮
                    Free.insert(Free.end(), x, lent[x].back()); 
                    while(have[i] and !Free.empty())    have[i]--, ans[Free.back()]++, Free.pop_back();
                }
            }
        }
        for(int i=1; i<=N; i++) sum -= ans[i];
        cout<< sum<< '\n';
        for(int i=1; i<=N; i++) cout<< ans[i]<< " \n"[i==N];
        return 0;
    }

}

int main() {
    Josh_zmf::main();
    return 0;
}