牛客小白月赛77 C题解 | 小Why的商品归位

发布时间 2023-09-01 21:30:30作者: six_one

原题链接

先不考虑车子的容量问题,因为结束位置保证是在起始位置之后的,那我们从前往后扫,发现是可以知道每个点时的车内的商品。

但是现在有了容量限制,我们怎么办呢,如果对于一段,k 都是大于每个点的货物量时,可以一趟装完,但是如果大于 k 就需要不知一次,可以发现所需的其实是该段的最大除以 k ,并上取整。

最终答案就是,每个点最大同时有的商品数量,除 k 上取整。

代码

    
void work()
{
    n = read(), m = read(), k = read();
    for(int i = 1; i <= m; i++)
    {
        int x = read(), y = read();
        a[x]++, a[y]--;
    }
    for(int i = 1; i <= n; i++)
        a[i] = a[i - 1] + a[i];
    for(int i = 1; i <= n; i++)
        ans = max(ans, a[i]);
    printf("%lld", ans % k == 0 ? ans / k : ans / k + 1);
     
    return;
}