解题思路
先把每个时刻真正还缺多少容量算出来。设
needi=max(0,ai−bi)
那么问题就变成：
- 每次启动一个扩容包，会在一段长度为 w 的连续区间内，每个时刻都额外提供 x 容量；
P4619.第4题-多多的扩容计划
题目内容
多多最近在做一条服务链路的大促扩容预案。他拿到了未来n个时间点的负载预测。
第i个时间点
- 业务需求为ai;
- 当前基础容量为bi
多多最多可以申请m个“临时扩容包”。每个扩容包都有相同的扩容量x。如果一个扩容包在第i个时间点启动，那么它会在从i开始的长度为w的时间区间，即时间点i,i+1,...,i+w−1上各额外提供容量，若区间超过第n个时间点，超出的部分无需考虑。多个扩容包可以在同一时刻启动，它们的效果也可以叠加。
请你求出最小的非负整数x，使得可以通过在启动不超过m个扩容包的情况下，让所有时间点都满足：基础容量+所有生效中的扩容包容量>=业务需求。
在得到最小可行的x之后，多多还想知道：在这个最小x下，最少需要启动多少个扩容包。如果无论怎样都无法满足全部时间点的业务需求，输出−1。
输入描述
第一行输入一个整数T，表示测试数据组数。
接下来对每组数据:
-
第一行输入3个整数n,m,w;
-
第二行输入n个整数a1，a2,...,an，表示各时间点的业务需求;
-
第三行输入n个整数b1，b2,...,bn，表示各时间点的基础容量
输出描述
对每组数据各输出一行:
- 若存在可行解，输出两个整数x,C，分别表示最小可行的单包扩容量，以及在该扩容量下最少需要启动的扩容包数量
- 若不存在可行解则输出-1
补充说明
1≤T≤3
1≤n≤106
0≤m≤106
1≤w≤n
0≤ai,bi≤109
单个测试用例中所有测试数据的n之和不超过106
样例1
输入
2
5 2 3
5 7 6 4 5
4 4 4 4 4
6 2 2
10 1 10 1 10 1
0 0 0 0 0 0
输出
3 2
-1
样例1
输入
3
1 1 1
5
2
3 4 3
13 13 13
1 1 1
5 1 4
0 0 0 0 6
0 0 0 0 0
输出
3 1
3 4
6 1
