Codeforces Round #666 (Div. 2) ------ Power Sequence

标签: 算法  Codeforce  c++  

题目

在这里插入图片描述

题意:

给定一个长度为n的序列,可以进行两种操作,求使其变为最佳序列的最小花费
操作一:排序,此操作没有花费
操作二:对任意一个数无限制的进行加一或者减一操作,每次花费为1个单元
最佳序列定义:a[i] = c^i,数组下标从0开始,即首项为1的等比数列

题解:

求出c的范围,暴力枚举即可。
根据题目给出的数据范围,可知这个数组的最大和为1e14,然而等比数列的增长是非常快的,因此很快便会打到上界,所以最大公比为pow(1e14, 1.0 / n)

AC代码:

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<map>
#include<string>
#include<math.h>
using namespace std;
#define ll long long
const ll inf = 1e15;
const int N = 1e5 + 15;
int a[N];
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	int c = pow(inf, 1.0 / n);
	ll ans = inf;
	for (int i = 1; i <= c; i++) {
		ll num = llabs(1 - a[0]);
		ll q = 1;
		for (int j = 1; j < n; j++) {
			q *= i;
			num += llabs(a[j] - q);
			if (num > ans)
				break;
		}
		ans = min(ans, num);
	}
	cout << ans << endl;
	return 0;
}
版权声明:本文为qq_43321732原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_43321732/article/details/108421114

智能推荐

1264页面推荐(中等 union all )稍微的难点在于找1的朋友

![在这里插入图片描述](https://img-blog.csdnimg.cn/20200904233840843.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTMxNTk0,size_16,color_FFFFFF,t...

单链表+单链表代码(链表最基础)

链表 链表是有顺序的表,在内存中存储: 链表是以节点的方式存储的 每个节点包括data域,next域:指向下一个节点 如图:发现链表的各个节点不一定是连续存放的,有跳跃的,不是连续存储 链表分为带头节点的链表和没有头结点的链表 添加: 1.先创建一个head头结点,作用就是单链表的头 2.后面每添加一个节点,就直接加入到链表最后 遍历: 代码 添加节点到链表里: 这里借助于temp节点,通过循环找...

Rtthread学习笔记(十三)RT-Thread Studio开启硬件看门狗Watchdog

一、开启硬件看门狗Watchdog 1、配置RT-Thread Settings 2、开启stm32f1xx_hal_conf.h中的宏定义 3.使用RT接口函数初始化硬件看门狗...

TYVJ 4864 天天去哪吃 || 清北学堂金秋杯大奖赛

题目描述: 记录一下i这个值上次出现的位置在哪里,就是pre...

java反编译

jvm 把Boolean类型的值flag当做int类型处理。​​​ Foo.java: 由 class 文件生成 jasm 文件:java -jar asmtools.jar jdis Foo.class > Foo.jasm  修改jasm文件: 执行反编译: java -jar jd-gui-1.6.6.jar File 打开Foo.class文件:b修改为2 重新执行java...

猜你喜欢

【学习笔记】03-v-html的学习和示例

v-html的认识和使用 示例: 显示结果: 注意:v-html是有复制的...

Java实现在线考试系统(系统介绍)

1.和现在有的考试系统有以下几种优势: a.和现在有的系统比较起来,本系统有科目、章节、老师、学生、班级等信息的管理,还有批阅试卷查看已批阅试卷等。传统的考试系统划分并不细,业务功能简单。 b.和学校的考试系统还有外面的考试系统比较起来,本系统是B/S结构,学校的考试系统一般为C/S结构,性能方面不如B/S结构,并且C/S接口需要安装客户端,客户端压力很大,我的系统只需要电脑具有浏览器,在同一局域...

计算机视觉--多视几何初步尝试

基础矩阵的原理 K和K’分别是两个相机的参数矩阵。p和p’是X在平面π的坐标表示。所以可以得出 具体计算过程 代码: #!/usr/bin/env python coding: utf-8 from PIL import Image from numpy import * from pylab import * import numpy as np from imp ...

java初学者怎么学习才可以快速入门

java初学者怎么学习才可以快速入门 一、了解JAVA 我们要知道:Java是由Sun Microsystems公司于1995年5月推出的Java面向对象程序设计语言。 Java之父:詹姆斯·高斯林 1.1 java的三个体系 Java SE(Java Platform Standard Edition)。Java SE 以前称为 J2SE。它允许开发和部署在桌面、服务器、嵌入式环境...

字段属性之主键&增删改查&自增长&唯一键约束

字段属性之主键&自增长&唯一键约束 主键 主键:primary key 主要的键 一张表中只有一个字段可以使用对应的键,用来唯一的约束该字段里面的数据,不能重复,这种称之为主键 一张表只能最多一个主键 增加主键 SQL操作中有多种方式增加主键大体分为三种 1.在创建表的时候直接在字段之后跟primary key关键字(主键本身不允许为空) 优点:非常直接:缺点:只能使用一个字段作为...