Candy Cane Feast (USACO Bronze 2023 December)

12月的USACO考试是每年四次中的第一次，一般来说难度最低，这次也不例外，是升级的好机会。

对于测试点2-10来说: 直接模拟就能够通过。

怎么得到全部分呢？直接模拟的复杂度是 $\mathcal{O}(NM)$ 的，是否有办法可以直接降低复杂度？想了一下好像并不直观，有些Bronze级别的题，理论复杂度就是比较高，这时候可以想一下是否有启发式规则(heuristics)，可以节省计算。

直观想前几个牛会吃掉大部分，而且最高的牛之后的吃不到任何东西
所以维护一个最高牛的位置，对于每根甘蔗，只用计算到这头牛就可以结束，应该可以省掉很多计算

使用这个办法之后，还有两个TLE，需要再优化一下。

我们观察到一个更简单的heuristics是：如果当前的cane已经被全部吃光了，后面的牛就不用再看了，直接进入下一根cane就行了，这时可以直接break循环。加入这次个之后就通过了。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, m;
ll cows[200005], canes[200005];
int tallest;
ll height;
 
int main() {
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++) {
        scanf("%lld", &cows[i]);
        if (cows[i] > height) {
            height = cows[i];
            tallest = i;
        }
    }
    for (int i = 0; i < m; i++)
        scanf("%lld", &canes[i]);
 
    for (int i = 0; i < m; i++) {
        ll bottom = 0;
        int end = tallest;
        for (int j = 0; j <= end; j++) {
            ll eat = 0;
            if (cows[j] > bottom)
                eat = min(cows[j], canes[i]) - bottom;
            bottom += eat;
            cows[j] += eat;
            if (cows[j] > height) {
                height = cows[j];
                tallest = j;
            }
            if (bottom == canes[i])  
                break;
        }
    }
    for (int i = 0; i < n; i++)
        printf("%lld\n", cows[i]);
 
    return 0;
}