首页 > 其他分享 >每日一题-思维

每日一题-思维

时间:2022-12-25 22:14:27浏览次数:61  
标签:思维 cout int max 每日 元素 cin ans 一题

CF Round #840-C.Another Array Problem

描述

给定一个包含\(n\)个元素的序列\(a\), 可以进行以下操作任意次:
选择下标\(i, j(1<=i<j<=n)\), 将所有\(a_k\)替换为\(|a_i-a_j|(i<=k<=j)\).
问序列能操作出的最大元素和.

思路

n>=4

对于\(n>=4\)时, 可以发现这样的一个特点:
对于任意相邻两元素, 做两次这种操作可使这两个元素都变为0.
以\(n=4\)为例:
1 3 4 7 -> 2 2 4 7 -> 0 0 4 7
1 3 7 4 -> 2 2 7 4 -> 0 0 7 4 -> 7 7 7 4 -> 7 3 3 3 -> 7 0 0 0 -> 7 7 7 7
当最大元素位于其他位置同理.

n=3

设各元素分别为\(a, b, c\)
有几种小情况:

  1. \(a\)最大, 那么答案可以取到\(3a\).

  2. \(c\)最大, 那么答案可以取到\(3c\).

  3. \(b\)最大, 那么答案可以取到\(max\{a+b+c, 3*(b-a), 3*(b - c)\}\).

n<=2

比较简单

代码

void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	
	for (int &i : a) {
		cin >> i;
	}
	
	if (n >= 4) {
		cout << n * *max_element(a.begin(), a.end()) << '\n';
	} else if (n == 2) {
		cout << max({a[0] + a[1], (a[0] - a[1]) * 2, (a[1] - a[0]) * 2}) << '\n';
	} else if (n == 3) {
		int ans = a[0] + a[1] + a[2];
		ans = max({ans, 3 * a[0], 3 * a[2]});
		if (a[1] > a[0]) {
			ans = max(ans, 3 * (a[1] - a[0]));
		}
		if (a[1] > a[2]) {
			ans = max(ans, 3 * (a[1] - a[2]));
		}
		cout << ans << '\n';
	} else if (n == 1) {
		cout << a[0] << '\n';
	}
}

标签:思维,cout,int,max,每日,元素,cin,ans,一题
From: https://www.cnblogs.com/whose-dream/p/17004686.html

相关文章

  • 每日食词—day061
    inactiveadj.不活动、非活动的、暂停、失活、不活泼的initializev.初始化pursuitn.追求、追捕、追击、追捧dominates支配、主导、占主导地位prettyadj......
  • OmniGraffle Pro好用的思维导图工具v7.21.2中文正式版
    omnigraffleproMac版是一款全新推出的思维导图软件,可以帮助用户绘制图表,流程图,组织结构图以及插图等,完美的将您的头脑风暴表达出来,功能十分强大。此版本内附注册机,可永久......
  • 每日算法之和为S的两个数字
    JZ57和为S的两个数字题目输入一个升序数组array和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,返回任意一组即可,如果无法找出这样的数字,......
  • 可以快速搭建的免费开源项目:直播带货、富文本笔记、思维导图、声音克隆、消息推送服务
    可以快速搭建的免费开源项目:直播带货、富文本笔记、思维导图、声音克隆、消息推送服务、文档协作等等。01PureLive一个想让直播回归纯粹的项目,没有礼物、粉丝团、弹窗,只有......
  • OI 思维与策略杂记 2022.12
    OI思维与策略杂记(一)这个系列的开坑,主要是为记录和总结一些比较典型或创新的有价值的思维与Trick。文内的题目有一定难度质量是很高的,...嗯其实更多是写给自己总结用的......
  • 每日食词—day060
    layoutn.布局、设计、布置balancen. v.平衡、均衡、天平upgradev. n. adj. adv.升级、升级版、系统升级、增加、提高directoriesn.目录、计算机文件或程......
  • 还在手动发早安吗?教你用java实现每日给女友微信发送早安
    摘要:教你如何用java实现每日给女友微信发送早安等微信信息。本文分享自华为云社区《java实现每日给女友微信发送早安等微信信息》,作者:穆雄雄。前言据说这个功能最近在......
  • [leetcode每日一题]12.24
    平安夜重磅回归,以后再也不摸鱼了。也曾经想过,每天花上一两个小时想一道题有什么意义吗,有的时候完全是往错误的方向想的,而且随之耽误的正事且破坏的心情实在很令人不爽。但是......
  • 还在手动发早安吗?教你用java实现每日给女友微信发送早安
    摘要:教你如何用java实现每日给女友微信发送早安等微信信息。本文分享自华为云社区《​​java实现每日给女友微信发送早安等微信信息​​》,作者:穆雄雄。前言据说这个功能最......
  • 每日算法之数组中只出现一次的两个数字
    JZ56数组中只出现一次的两个数字题目一个整型数组里除了两个数字只出现一次,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字思路算法实现既然有两个数......