先不考虑车子的容量问题,因为结束位置保证是在起始位置之后的,那我们从前往后扫,发现是可以知道每个点时的车内的商品。
但是现在有了容量限制,我们怎么办呢,如果对于一段,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;
}
标签:read,题解,77,牛客,取整,Why
From: https://www.cnblogs.com/six-one/p/17672884.html