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;
}
标签:传送,题目,idx,int,单元格,codeforces,1901B,操作,div2 From: https://www.cnblogs.com/Tom-catlll/p/17932988.html