首页 > 其他分享 >Codeforces Round #619 (Motarack's Birthday)

Codeforces Round #619 (Motarack's Birthday)

时间:2022-10-27 18:12:46浏览次数:55  
标签:Motarack 619 int Dark Birthday array include elements

题面

Dark is going to attend Motarack’s birthday. Dark decided that the gift he is going to give to Motarack is an array a of n non-negative integers.
Dark created that array 1000 years ago, so some elements in that array disappeared. Dark knows that Motarack hates to see an array that has two adjacent elements with a high absolute difference between them. He doesn’t have much time so he wants to choose an integer k (0≤k≤109) and replaces all missing elements in the array a with k.
Let m be the maximum absolute difference between all adjacent elements (i.e. the maximum value of |ai−ai+1| for all 1≤i≤n−1) in the array a after Dark replaces all missing elements with k.
Dark should choose an integer k so that m is minimized. Can you help him?

题意

给一个数列,其中缺少一些数,用-1替代,请填一个数替换掉-1,使得相邻两项之差的绝对值的最大值最小

分析

直接统计空位旁边的数的最大值最小值,取其平均值即可
另外也要考虑到非空位的两数差所以最后处理时遍历整个数组

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
inline int read() {
	register int x = 0, f = 1;
	register char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0',c = getchar();
	return x * f;
}
int a[100001];
int maxn,minn;
void work(int i){
	maxn = max(maxn, a[i]);
	minn = min(minn, a[i]);
}

int main() {
	int t = read();
	while (t--){
		minn = 0x3f3f3f3f, maxn = -0x3f3f3f3f;
		memset(a, 0, sizeof(a));
		int n = read();
		for (int i(1); i <= n; i++) {
			a[i] = read();
		}
		for (int i(1); i <= n; i++){
			if (a[i] == -1){
				if (i > 1 && a[i - 1] != -1) work(i - 1);
				if (i < n && a[i + 1] != -1) work(i + 1);
			}
		}
		int k = minn + maxn >> 1;
		int ans = 0;
		for (int i(1); i <= n; i++)
			if (a[i] == -1) a[i] = k;
		for (int i(1); i < n; i++)
			ans = max (ans, abs(a[i] - a[i + 1]));
		printf("%d %d\n", ans, k);
	} 
	return 0;
}

标签:Motarack,619,int,Dark,Birthday,array,include,elements
From: https://www.cnblogs.com/cancers/p/16833229.html

相关文章

  • 619 Javascript_对象_Date and 620 Javascript_对象_Math
    Javascript_Boolenan1.创建  newBoolean(value);   //构造函数  Boolean(value);      //转换函数2.方法toStri......
  • NEUOJ 1207(Birthday present-前缀和)
    给你一个数组a,给你一个k,你可以讲每个数减去不超过k,要求最后的GCD最大,求这个gcd1 ≤ n ≤ 3·1e5; 1 ≤ k ≤ 1e61 ≤ ai ≤ 1e6显然min(ai)<=k时,答案为min......
  • Happy Second Birthday Jenkins X!
    始于2019年初的JenkinsX项目在去年的1月14号庆祝了它的第一个生日,这对任何开源项目来说都是一件大事,我们刚刚又庆祝了它的第二个生日。JenkinsX的两周年!JenkinsX已......
  • P7619 [COCI2011-2012#2] RASPORED
    此题解使用平衡树解决。1、原始情况首先,我们考虑未修改的情况。设\(L_i\)为吃饭时间,\(a_i\)为制作所需时间。对于\(n\)个居民,假设我们不对做披萨的顺序进行修改,即按......
  • 竞赛-6194. 最小 XOR
    解题思路 1、二进制中num的1的数量等于num2中的1的数量 2、num1中二进制,和num前面相同,后面不同,这样异或操作后得到的最小, 3、相同部分不变,不同部分都是0,如果还有1......
  • 竞赛6193. 沙漏的最大总和
    今天参加竞赛,被第4道题虐了,继续学习给你一个大小为mxn的整数矩阵grid。按以下形式将矩阵的一部分定义为一个沙漏:返回沙漏中元素的最大总和。注意:沙漏无法旋......
  • EG2124A替代FD6288、PT5619,260V0.8A三相立半桥驱动芯片
    1. 特性  悬浮自举电源设计,耐压可达 260V  集成三路立半桥驱动  适应 5V、3.3V 输入电压  高频率支持 500KHZ  低端 VCC 电压范围 4.5V-20V  输出电流......
  • 好路径数目-Leetcode6191
    好路径数目题目描述给你一棵n个节点的树(连通无向无环的图),节点编号从0到n-1且恰好有n-1条边。给你一个长度为n下标从0开始的整数数组vals,分别表示每......
  • acwing 4619. 减法操作
    acwing4619.减法操作原题链接:https://www.acwing.com/problem/content/4622/思路这个题两种操作顺序是先进行哪个操作都是可以的。第一个操作将某个数减2,只要是偶数就......
  • 双哈希_Birthday_Cake
    BirthdayCake思路:找到每个串的公共前后缀,统计公共前后缀之间的字符串的hash值,并判断所给n个串中是否存在符合条件的串eg:abbddab对于该串,我们不难发现,公共前后缀是ab,公......