题目链接

https://codeforces.com/problemset/problem/1700/D

题目描述

有 $n$ 个容器，第 $i$ 个容器容量为 $v_i$ 升，可以容纳 $[0,v_i]$ 升的水。

满出去的水会将从容器 $i$ 转移到容器 $i+1$，如果 $i+1$ 也满了会转移得更远。满出最后一个容器的水会倒到河中。

现在要将所有容器填满。你可以选择一些容器注水，让这些容器每秒进入一升水。$q$ 次询问，问最初所有容器都是空的，最少选择多少个容器注水使得 $t_i$ 秒内能填满所有容器。

$1\le n,q\le 2\times 10^5$，$1\le v_i,t_i\le 10^9$。

输入输出样例

输入样例1

5
4 1 5 4 1
6
1
6
2
3
4
5

输出样例

-1
3
-1
-1
4
3

输入样例

5
4 4 4 4 4
6
1
3
6
5
2
4

输出样例

-1
-1
4
4
-1
5

思路

先考虑不能注满的情况，假设把n个水阀全部打开，计算所有的容量和sum，如果需要的平均时间$avg=\lceil sum/n\rceil$，如果 $avg$ 小于 $t$ ，那么在 $t$ 秒内肯定不能注满。

但是，如果 $avg$ 大于等于 $t$，是否就一定能注满呢？
答案的否定的，由题目中的限定条件可知，水流只能从 $i$ 流到$i+1$处，我们以数据 1155 为例。
$avg=12/4=3$

数据排列为1155时，3 秒能注满，$v_1$ 和 $v_2$ 的水会流到 $v_3$ 和 $v_4$ ；
数据排列为1551时，3 秒不能注满，注入$v_4$时会流走2升的水，需要4 秒才能注满；
数据排列为5511时，需要5秒才能注满，因为$v_1$必须要注5秒。

通过上面的例子我们可以发现，如果要注满所有容器，不能从总容量入手，我们可以计算每一个阶段的前缀和，计算其平均值，然后求出最大的平均值，这个最大的平均值就是所要求的最低时间。

当然，如果 $avg$ 大于等于这个最大平均值，我们直接输出$avg$即可。

参考代码

#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;
long long sum=0;
int main(){
	//freopen("1700D.txt","r",stdin);
	int t,n,temp,maxVal=0,pos,avg;
	
	scanf("%d",&n);
	sum = 0;
	for(int i = 1; i <= n;i++) {
		scanf("%d", &temp);
		sum += temp;
		avg = ceil (sum*1.0/i);
		maxVal = max(maxVal,avg);
		
	}
	
	int q, ans;
	scanf("%d" , &q);
	for( int i = 1; i <= q; i++) {
		scanf("%d", &temp);
		ans = ceil(sum*1.0/temp);
		if (temp < maxVal) cout << -1 <<endl;
		else  cout<< ans <<endl;
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30