链接
传送门
代码
#include
using namespace std;
typedef long long LL;
const int N=2e5+10;
LL a[N],c[N];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
LL sum=0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&c[i]);
a[i]=c[i]-c[i-1];
if(a[i]>0)
{
sum+=a[i];
}
}
if(n==1) printf("%lld\n",c[1]-1);
else
{
printf("%lld\n",sum-1);
}
}
return 0;
}
总结
1.题意是说，原来有若干个格子，每一个格子的初始值都是0，可以进行两种操作，第一种操作是从左至右把格子上的数字增加一，第二种操作是跳转到某一个格子，把该格子的数值增加一
2.问需要跳转多少次可以使得格子上的数字变成输入的那样
3.如果c[i]>=c[i+1]，就不需要考虑i+1这个格子，因为增加到i个格子的时候，自然增加1就可以到达下一个格子，不需要进行跳转就可以满足下一个格子的要求（分析到这里发现，本来要分析所有的格子，这里简化为了分析两个一般化的格子）
4.如果c[i] 5.递推的思路，每一次把前面的处理好，相当于每一次只需要考虑两个格子的情况，构建一个差分数组，数组下标从1开始计数，每一个c数组元素对应一个a数组元素（差分数组），差分数组是当前元素减去前面一个元素，从1开始计数，1前面一个元素被初始化为0了，所以不会影响构建差分数组。 6.如果后面一个格子大于前面一个格子，体现在差分数组里面就是，差分数组的元素大于零，我们把大于零的差分数组的元素求和，就是最后的答案 7. #include using namespace std; const int N=2e5+10; typedef long long LL; LL a[N],c[N]; int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); LL sum=0; for(int i=1;i<=n;i++) { scanf("%lld",&c[i]); a[i]=c[i]-c[i-1]; if(a[i]>0) { sum+=a[i]; } } printf("%lld\n",sum-1); memset(a,0,sizeof a); memset(c,0,sizeof c); } return 0; } 8.初始化数组防止上一次循环对当前循环造成影响，c数组的单个元素的大小是1e9，求和之后会超过int的数据范围，所以要使用long long，最后输出的答案是sum-1，因为第一次不需要跳转，所以减去1 精彩内容
您阅读本篇文章共花了：
发表评论