B、Chip and Ribbon

跳转原题点击此：该题地址

1、题目大意

存在一条由n个单元格组成的带子。chip可以做两个操作：1、由 \(i\) 走到 \(i+1\) ，但是不能走到 \(i-1\)；2、可以传送到任意位置，包括传送到原地。每到一个单元格，该单元格的数值+1（初始为0）。最开始chip在从第一格开始走起（题目保证第一格 \(\ge\) 1）。问你要实现给定输入的序列，至少要传送几次。

2、题目解析

一道区间贪心题目。只要第\(i+1\)个数比第\(i\)个数大，那么肯定是要传送\(f[i+1] - f[i]次\)。如果小于等于则不需要因为可以由其前面的数执行操作一实现。那么如何确保后面的数的传送次数不重复，我们可以用一个变量记录前一个数的大小。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 2e5+10;

int T;
int n;
int f[N];

void solve()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >>	f[i];
		
	ll ans = 0, idx = 1;	// 初始直接从1开始，所以默认无需传送实现一次操作一
	for(int i = 1; i <= n; i++)
	{
		if(f[i] > idx)			// f[i]的操作无法依靠前面idx个操作一实现，需要传送
		{
			ans += f[i] - idx;
			idx = f[i];			// 更新为传送后的操作数
		}
		else					// 说明仅仅依靠操作一就能实现
			idx = f[i];
	}
	cout << ans << endl;
	
}

int main()
{
	cin >> T;
	while (T--)
	{
		solve();
	}

	return 0;
}