首页 > 其他分享 >Codeforces 1987C

Codeforces 1987C

时间:2024-07-23 23:08:11浏览次数:13  
标签:max int 1987C 元素 Codeforces 步骤 ++ printf

codeforces P1987C

给定一个n长度的数组,每一步都要遍历整个数组。如果某个元素是末尾元素或是比其后一个元素大,则该元素减去1直到该元素为0,求解总步数,算法复杂度要求 \(O(n)\)

先给出暴力解法,复杂度 \(O(n^2)\):

	int t = 0;
	do{
		for(int i = 0; i < n - 1; i++){
			if(a[i] > a[i + 1]) a[i] = max(0, a[i] - 1);
		}
		a[n - 1] = max(0, a[n - 1] - 1);
//		printf("-----\n");
//		for(int i = 0; i < n; i++) printf("%d ", a[i]);
//		printf("\n-----\n");
		t++;
	}while(!jugde(a, n));
	return t;

显然会Time limit exceeded,所以要使用不同的算法
考虑到题述中的关键步骤 “如果某个元素是末尾元素或是比其后一个元素大,则该元素减去1直到该元素为0”,可以看到:
1)整个数组中非最大的数字的减少步骤一定包括在最大数字的减少步骤中,如果这个最大数字在第一个。
2)这个最大的数字若不是在第一个,则会存在额外(在这个最大数字之外)的减少步骤。
整个模拟的过程都是在向右比大,但末尾元素却会一直减小,说明了什么。

说明整个模拟过程中,不受条件约束的持续变化的那个元素的位置,应该是数组遍历的起点,因为它代表了一个确定存在的减少步骤

所以应该对整个数组逆向遍历,动态规划方程为:

\[ans=\max(ans+1,h_i) \]

解释一下:
1)当前的步骤小于该高度 \(h_i\) 时,说明这不是上述的“最大数字的减少步骤”,将其替换
2)当前的步骤大于该高度 \(h_i\) 时,说明该高度的减少步骤被包含在最终的减少步骤里,对应了最后的 1 -> 0,则ans + 1

所以代码为:

	int n, t = 0;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
	
	for(int i = n - 1; i >= 0; i--) t = max(t + 1, a[i]);
	
//	printf("%d\n", t == pat(a, n) ? t : -1); //对拍
	printf("%d\n", t);

AC

标签:max,int,1987C,元素,Codeforces,步骤,++,printf
From: https://www.cnblogs.com/hanknie/p/18319820

相关文章

  • Codeforces Round 957 (Div. 3)复盘
    今天打了一下DIV3,专业转了就是不一样T1Onlypluses这道题主要就是理解乘法分配律,最多的绝对是两数相乘数最大的。T2AngryMonkey这道题一遍AC,虽然很简单还是值得鼓励,主要还是数学问题,用笔写下来找到数学规律之后做起来就很快T3GorillaandPermutation这道题还是很简单......
  • Codeforces Round 952 (Div. 4)复盘
    第一次打比赛的总结Q1CreatingWords这道题其实主要考的就是对于输入语句的理解,最开始我想的是运用scanf,puts,一个语句一个语句的去读取,但是确实对各个输入语句的了解过于肤浅了,特别是哪个读不读空格之类的,其实也算是没有把题目看清楚,它的难度其实没有自己以为的那么难,因为是限......
  • Codeforces 2400+ flows 大杂烩
    CF903GYetAnotherMaxflowProblem2700关键点:最大流转最小割显然我们需要用其他方式维护最大流,考虑到最大流等于最小割,于是我们去求最小割。考虑这个图的特性不难发现左边和右边两列都至多割掉一条边,于是我们直接枚举割掉的位置,剩下的左边前缀和右边后缀所有相连的边都要割......
  • Codeforces Round 960 (Div. 2)
    xht真的好强好强,好厉害这场打得有点史,共四发罚时还是抽象了,如果没有xht就真的完了呜呜。不过也说明我是真的菜,还有把做法想出来之后验证不到位。A.SubmissionBait罚时了,15min才过/lh稍微想一下可以知道,对于最大数\(x\),若其出现次数为奇数,那么A是必胜的,反之则只能从更小......
  • [Codeforces Round 960 (Div. 2)]A-E
    CodeforcesRound960(Div.2)A-EA题意:公平博弈。给定一个数组n个数,每个数只能用一次。给一个\(mx\)。每次轮到自己操作的时候就选一个数组里的数,满足\(a[i]>=mx\),然后令\(mx=a[i]\).双方轮流做直到一方无法操作,则另一方取胜。Sol:赛时1min猜了个错解,只看最大值,只看最大值的出......
  • Codeforces Round 958 (Div. 2)
    Preface周末补题计划的最后一场,这场由于是最古早的所以有些题题意都记不太清了赛时经典发病,前四题一题WA一发,然后把时间打没了E题经典没写完(中间还抽空写了个假做法),邮电部诗人了属于是A.SplittheMultiset刚开始还感觉无从下手,写了个记搜交上去还WA了,后面发现每次分......
  • Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)
    Preface这场比赛的时候CF一直抽风,快10min的时候才登上去,然后中间交题也一直在人机验证50min左右过了前5题后,F没想到生成树当场趋势了,赛后发现原来是原题大战可海星A.DiverseGame将每个数循环移位变为下一个数即可,注意特判\(n=m=1\)的情形#include<cstdio>#incl......
  • Codeforces Round 958 (Div. 2)
    A.SplittheMultisetForexample, {2,2,4} isamultiset.Youhaveamultiset ......
  • Codeforces Round 960 (Div. 2)(A - D)
    CodeforcesRound960(Div.2)(A-D)A-SubmissionBait解题思路:假设直接选最大数,如果最大数有奇数个,\(Alice\)必胜,反之必败。根据这个思路,从大到小看数字,找到第一个出现奇数次的数,从它开始选,就能保证每次\(Alice\)选的时候还剩奇数个选项。代码:#include<bits/stdc++.......
  • Codeforces Round 960 (Div. 2)
    Preface周日开始补之前欠下的CF博客,这周一共有三场就按照从后往前的顺序补吧这场经典前期唐完了,前4题上来每题WA一发也是神人了,最后做到E的时候只有50min了结果还把题看错了以为树的形态都是不确定的,怀疑人生了好久感觉这个题完全没法做,后面看了眼样例才发现树的形态......