CF 1901B Chip and Ribbon 学习笔记

链接

传送门

代码

#include<bits/stdc++.h>
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]<c[i+1]，需要考虑i+1这个格子，而且必须进行跳转才能满足要求，假设增加到i个格子满足要求，然后增加1，使得i+1个格子的数值和i个格子的数值相等，此时，i+1格子还需要增加(c[i+1]-c[i])才可以满足要求

5.递推的思路，每一次把前面的处理好，相当于每一次只需要考虑两个格子的情况，构建一个差分数组，数组下标从1开始计数，每一个c数组元素对应一个a数组元素（差分数组），差分数组是当前元素减去前面一个元素，从1开始计数，1前面一个元素被初始化为0了，所以不会影响构建差分数组。

6.如果后面一个格子大于前面一个格子，体现在差分数组里面就是，差分数组的元素大于零，我们把大于零的差分数组的元素求和，就是最后的答案

7.

#include<bits/stdc++.h>
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