水壶(【CCF】NOI Online能力测试3 提高组) |
您所在的位置:网站首页 › 1个杯子 › 水壶(【CCF】NOI Online能力测试3 提高组) |
题目描述
有 n个容量无穷大的水壶,它们从 1∼n 编号,初始时 i 号水壶中装有Ai 单位的水。 你可以进行不超过 k 次操作,每次操作需要选择一个满足 1≤x≤n−1 的编号 x,然后把 x 号水壶中的水全部倒入 x+1 号水壶中。 最后你可以任意选择恰好一个水壶,并喝掉水壶中所有的水。现在请你求出,你最多能喝到多少单位的水。 输入格式第一行一个正整数 n,表示水壶的个数。 第二行一个非负整数 k,表示操作次数上限。 第三行 n 个非负整数,相邻两个数用空格隔开,表示水壶的初始装水量 A1, A2, ⋯, An。 输出格式一行,仅一个非负整数,表示答案。 输入样例 10 5 890 965 256 419 296 987 45 676 976 742 输出样例 3813 数据规模与约定1.要想最多能喝到多少单位的水,很显然每次倒水之后,那么肯定要把这个更多的水,倒到下一个水壶里面去,所以说一定是连续水壶水的和(注意 k 次操作是k+1个水壶的和) 2.那么题意可以简化为: 给定一个数列与区间长度,求数列中最大的区间和 (1)暴力 O (n^2) 但n=10^6时肯定会爆炸 (2)前缀和优化 O (n) 那我们就可以想到用前缀和完美解决 (传送门:一维前缀和) AC的C++代码如下: #include using namespace std; int A[1000010],sum[1000010];//A为水壶的初始装水量,sum为前缀和 int main() { int n,k; cin>>n>>k; for(int i=1;i>A[i]; sum[i]=sum[i-1]+A[i]; } int max=sum[k+1];//连续k+1个水壶 for(int i=1;i |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |