1B.小a与204(C++)

2023-12-02 22:58
文章标签 c++ 1b 204

本文主要是介绍1B.小a与204(C++),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

小a与"204"(C++)

点击做题网站链接

题目描述
小a非常喜欢204这个数字,因为′a′+′k′=204。
现在他有一个长度为n的序列,其中只含有2,0,4这三种数字
设ai为序列中第i个数,你需要重新排列这个数列,使得 ∑ i = 1 n ( a i − a i − 1 ) 2 \sum_{i=1}^n (a_i−a_{i−1})^2 i=1n(aiai1)2最大(公式的含义是:每个数与前一个数差的平方的和)
注意:我们默认 a 0 a_0 a0=0

输入描述:
第一行一个整数n
接下来一行n个整数,第i个数表示 a i a_i ai

输出描述:
输出一个整数,表示 ∑ i = 1 n ( a i − a i − 1 ) 2 \sum_{i=1}^n (a_i−a_{i−1})^2 i=1n(aiai1)2的最大值

示例1
输入
2
2 4

输出
20

说明
样例1解释:按(4,2)排列是最优的,此时 s u m = ( 4 − 0 ) 2 + ( 2 − 4 ) 2 = 20 sum=(4−0)^2+(2−4)^2=20 sum=(40)2+(24)2=20

示例2
输入

3
2 0 4

输出
36

说明
样例2解释:按(4,0,2)排列是最优的,此时 s u m = ( 4 − 0 ) 2 + ( 0 − 4 ) 2 + ( 2 − 0 ) 2 = 36 sum=(4−0)^2+(0−4)^2+(2−0)^2=36 sum=(40)2+(04)2+(20)2=36

示例3
输入

5
2 4 0 2 4

输出
52

备注:
1 ⩽ n ⩽ 1 0 5 1⩽n⩽10^5 1n105,保证 a i a_i ai为2/0/4中的数

题目解析:
贪心算法
一个显然的构造策略是首先放置4, 0, 4, 0,直到其中一个用光。
接下来如果4多余,那么可以按4, 0, 4, 0, … , 4, 2, 4, 2, …(先4后2)的方法构造
如果0多余,可以按照4, 0, 4, 0 … 4, 0, 2, 0, 2 …(先2后0)的方法构造
实际上此题还可以推广到更一般的情况,也就是第一个位置放最大的,第二个位置放最小的,第三个位置放第二大的以此类推,这种思路写起来也会更简单一些。
所以,我们只需要记录下2/0/4分别出现的次数,并且每次找到记录匹配就行。其实这样我们可以把数字从大到小排序,并且使用两个标记,一个从前向后依次位移,一个从后向前依次位移,直到两个重合结束,那么前面那个标记肯定先计数4,后面那个标记肯定先计数0,等4和0用完,自然就剩2了。

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;bool com(int a,int b) { return a>b; }
const int N = 1e5 +5;int main()
{long long int n,temp=0;int a[N];cin >> n;for(int i=0;i<n;++i) cin >> a[i];sort(a,a+n,com);if(n==1)//如果只有一个数字{temp += a[0]*a[0];cout << temp << endl;return 0;}int Count = 0;for(int i=0,j=n-1;i<j;)//i,j两个标记位移,当i<j时执行循环,特别注意i和j在什么特殊的情况下会+1,而不是每次都+1{if( Count!=0 )//如果是不是第一次进来{temp += pow((a[i]-a[j]),2);if( Count%2==1 ) ++i;if( Count%2==0 ) --j;}else//如果是第一次进来{temp += a[0]*a[0];}Count++;}cout << temp << endl;return 0;
}

这篇关于1B.小a与204(C++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/447151

相关文章

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window

从入门到精通C++11 <chrono> 库特性

《从入门到精通C++11<chrono>库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段(Durat

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多,因为它实际属于c++20最为重要的

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》:本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识:传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决

C++11委托构造函数和继承构造函数的实现

《C++11委托构造函数和继承构造函数的实现》C++引入了委托构造函数和继承构造函数这两个重要的特性,本文主要介绍了C++11委托构造函数和继承构造函数的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、委托构造函数1.1 委托构造函数的定义与作用1.2 委托构造函数的语法1.3 委托构造函

C++11作用域枚举(Scoped Enums)的实现示例

《C++11作用域枚举(ScopedEnums)的实现示例》枚举类型是一种非常实用的工具,C++11标准引入了作用域枚举,也称为强类型枚举,本文主要介绍了C++11作用域枚举(ScopedEnums... 目录一、引言二、传统枚举类型的局限性2.1 命名空间污染2.2 整型提升问题2.3 类型转换问题三、C