NC16137. 相邻的糖果
描述
输入描述
第一行三个数字n, m, x(2 ≤ n,m ≤ 106,1 ≤ x ≤ 109)。
第二行n个数字(1 ≤ ai ≤ 109)。
输出描述
输出一个操作数，代表实现要求的最少操作数。
示例1
输入:
3 2 3 2 1 2
输出:
0
说明:
2 1 2满足题目要求，任意相邻的两个数值之和均不超过3，所以不需要进行任何操作。C++14(g++5.4) 解法, 执行用时: 326ms, 内存消耗: 17788K, 提交时间: 2020-08-31 09:10:26
#include<iostream>
using namespace std;
int main()
{
long long int n,m,x,tot=0,ans=0;
cin>>n>>m>>x;
long long int a[n+1];
for (int i=1;i<=n;i++)
{
cin>>a[i];
tot+=a[i];
if (i>m)
tot-=a[i-m];
if (tot>x)
{
a[i]-=tot-x;
ans+=tot-x;
tot=x;
}
}
cout<<ans;
}
C++11(clang++ 3.9) 解法, 执行用时: 476ms, 内存消耗: 17792K, 提交时间: 2020-03-29 15:48:13
#include<iostream>
using namespace std;
int main()
{
long long int n,m,x,tot=0,ans=0;
cin>>n>>m>>x;
long long int a[n+1];
for(int i=1;i<=n;i++)
{
cin>>a[i];
tot+=a[i];
if(i>m)
tot-=a[i-m];
if(tot>x)
{
a[i]-=tot-x;
ans+=tot-x;
tot=x;
}
}
cout<<ans;
}