首页 > 其他分享 >codeforces刷题(1100):1901B_div2

codeforces刷题(1100):1901B_div2

时间:2023-12-28 16:49:29浏览次数:55  
标签:传送 题目 idx int 单元格 codeforces 1901B 操作 div2

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

相关文章

  • codeforces刷题(1100):1902B_div2
    B、GettingPoints跳转原题点击此:该题地址1、题目大意  Monocarp为了完成总共n天的某学期的p学分任务。Monocarp每天可以选择两种度过方式:上一次课和完成最多两个任务或者休息一天。其中上课获得l学分,每个任务获得t学分,其中任务不可以重复接取,并且每周获得一个新的任务(第一......
  • 「题解」Codeforces 1427G One Billion Shades of Grey
    感谢127的指导/ll\(|h_u-h_v|=\max(0,h_u-h_v)+\max(0,h_v-h_u)\),那么可以把它看成这样的问题:\[\min\{\sum_{(u,v)}\max(0,h_u-h_v+w_{u,v})c_{u,v}\}\]对偶一下,问题就变为:如果两个格子相邻就互相连容量为\(c_{u,v}=1\),费用为\(w_{u,v}=0\)的边,跑最大费用循环流。为了限......
  • codeforces刷题(1100):1904B_div2
    B、CollectingGame跳转原题点击此:该题地址1、题目大意  获得一个由n位正整数组成的数组。你可以选择选择任意一个数作为你的判断值。然后任意一个\(\le\)它的数可以被选中加入你的分数(注意判断值不算在里面),同时该数被移除数组。你的任务是,对于该数组中的每个数,都将其作为......
  • codeforces刷题(1100):1905B_div2
    B、Begginer'sZelda跳转原题点击此:此题地址1、题目大意  给你一个子树,你可任意选择两个节点\(u、v\),这两个节点之间的所有节点(包括\(u、v\))都将结合变为一个新的节点。要求你通过该操作将所有的节点变为只有一个节点,求最小的操作数。2、题目解析  由题意可得:当\(u、v\)......
  • CodeForces 1917E Construct Matrix
    洛谷传送门CF传送门\(2\nmidk\)显然无解。若\(4\midk\),发现给一个全\(2\times2\)子矩形全部异或\(1\)不会对行异或和和列异或和造成影响。那么我们找到\(\frac{k}{4}\)个全\(0\)的\(2\times2\)子矩形填\(1\)即可。否则若\(k=2\)或\(k=n^2-2\)......
  • CodeForces 1917F Construct Tree
    洛谷传送门CF传送门考虑形式化地描述这个问题。先把\(l\)排序。然后相当于是否存在一个\(\{1,2,\ldots,n\}\)的子集\(S\),使得:\(\sum\limits_{i\inS}l_i=d\)。\(\existsT\subseteqS,\max\limits_{i\notinS}l_i\le\min(\sum\limits_{i\inT}l_i,\sum......
  • Codeforces Round 915 (div2) E
    E.TreeQueries[题目链接](https://codeforces.com/contest/1904/problem/EProblem-E-Codeforces)题意概括:给定一棵大小为\(n\)的树,回答如下询问,询问之间相互独立:给定一个点\(x\)与\(k\)个点\(a_i\),求出从\(x\)出发不经过任何一个\(a_i\)的最长简单路径长度......
  • codeforces刷题(1100):1917B_div2
    模板B、EraseFirstorSecondLetter跳转原题点击此:该题地址1、题目大意  给你一个字符串,可以执行任意次以下操作,生成最终的字符串(不可为空),问你能生成的不重复字符串数为多少。操作一:删除字符串第一个字符;操作二:删除字符串第二个字符。2、题目解析  发现,操作一:即选......
  • Codeforces 1909G - Pumping Lemma
    这个题思考角度很多,做法也很多。这里介绍一种@asmend和我讲的做法。设\(d=m-n\),那么我们枚举\(|x|=i,|y|=j\),设\(s,t\)的LCP长为\(l_1\),LCS长为\(l_2\),那么可以得到这组\((i,j)\)合法的充要条件是:\(i\lel_1\)\(m-i-j-d\lel_2\)。\(d\bmodj=0\)。\(t[i,i+d-1......
  • Codeforces1917F - Construct Tree
    Codeforces1917F-ConstructTreeProblems给一个长度为\(n\)的序列\(l\)和\(d\)。要求判断是否可以构造出一颗节点数为\(n+1\)的树,满足\(l\)的每一个元素唯一对应为一条边的长度,并使整棵树的直径长度恰好为\(d\)。Solution不妨令\(l_1\lel_2\le\cdots\lel_......