1014 - Absolute Defeat
Time Limit：2s Memory Limit：64MByte
Submissions：257Solved：73
DESCRIPTION
Eric has an array of integers
a1,a2,...,ana1,a2,...,an.
Every time, he can choose a contiguous subsequence of length
kk
and increase every integer in the contiguous subsequence by
11.He
wants the minimum value of the array is at least
mm.
Help him find the minimum number of operations needed.
a1,a2,...,ana1,a2,...,an.
Every time, he can choose a contiguous subsequence of length
kk
and increase every integer in the contiguous subsequence by
11.He
wants the minimum value of the array is at least
mm.
Help him find the minimum number of operations needed.
INPUT
There are multiple test cases. The first line of input contains an integer
TT,
indicating the number of test cases. For each test case:The first line contains three integers
nn,
mm
and kk
(1≤n≤105,1≤k≤n,1≤m≤104)(1≤n≤105,1≤k≤n,1≤m≤104).The
second line contains nn
integers a1,a2,...,ana1,a2,...,an
(1≤ai≤104)(1≤ai≤104).
TT,
indicating the number of test cases. For each test case:The first line contains three integers
nn,
mm
and kk
(1≤n≤105,1≤k≤n,1≤m≤104)(1≤n≤105,1≤k≤n,1≤m≤104).The
second line contains nn
integers a1,a2,...,ana1,a2,...,an
(1≤ai≤104)(1≤ai≤104).
OUTPUT
For each test case, output an integer denoting the minimum number of operations needed.
SAMPLE INPUT
32 2 21 15 1 41 2 3 4 54 10 31 2 3 4
SAMPLE OUTPUT
1015
源代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<deque>
#include<map>
#include<set>
#include<algorithm>
#include<string>
#include<iomanip>
#include<cstdlib>
#include<cmath>
#include<sstream>
#include<ctime>
using namespace std; typedef long long ll;
int ans[200005]; int main()
{
int t;
int n,m,k;
int temp;
ll sum;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
sum = 0;
memset(ans,0x3f3f3f3f,sizeof(ans));
for(int i = 0; i < n; i++)
scanf("%d",&ans[i]);
for(int i = 0; i < n; i++)
{
if(ans[i]<m)
{
temp=m-ans[i];
sum+=temp;
for(int j = i; j < i+k;j++)
ans[j]+=temp;
}
}
printf("%lld\n",sum);
}
return 0;
}