CF1420C1 Pokémon Army (easy version) 题解

一道模拟题~

题目传送门

题目意思：

给出一个序列 $a$，然后我们要从 $a$ 里面求出一个单调递增的序列 $b$，使得按照题目中一减一加的方法求出来的答案最大。

思路：

1. 我们可以先用贪心的思路去想。因为要一减一加，所以我们尽量加大的数，减小的数。
2. 按照上面的说法，我们就遍历整个序列 $a$，每次判断当时是要加还是减，然后进行相应的操作就行了。

注意：因为 $a_i$ 最大能达到 $3\times 10^5$，所以用来计算的变量要开 long long。

代码：

#include<iostream>
using namespace std;
const int N=1e6+10;
int a[N];
int t,n;
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=0;i<=n;i++)
			cin>>a[i];
		a[n+1]=0;
		int up=0,down=0;//记录应该加还是减
		long long sum=0;
		for(int i=1;i<=n+1;i++)
		{
			if(a[i]>a[i-1])//如果当前的数大于上一个数，证明上一个阶段的最小数就是上一个数
			{
				if(down)sum-=a[i-1];
				down=0;
				up=1;
			}
			if(a[i]<a[i-1])//如果当前的数小于上一个数，证明上一个阶段的最大数就是上一个数
			{
				if(up)sum+=a[i-1];
				down=1;
				up=0;
			}
		}
		cout<<sum<<endl;
	}
	return 0;
}

完美撒花~