[Codeforces Round #666 (Div. 2)] B. Power Sequence 暴力枚举


题目链接:B. Power Sequence
题意

给你一个长度为n的序列a,让你通过一些操作使其变成一个叫“power sequence”的序列——存在一个c使得(0≤i≤n-1),

ai=ci{a_i=c^i}

ai​=ci。

    你能够更改序列里每个元素的位置,这个操作不计入操作数内。
    你可以选择任意一个元素增加或减少1,每进行一次这个操作,操作数+1。

问最少需要多少操作数使其变为“power squence”。

题解

本题我们先来分析,

ai1e9n1e5{a_i≤1e9,n≤1e5}

ai​≤1e9,n≤1e5。
那么我们能得出一个结论,操作数不可能超过

1e14{1e14}

1e14,因为当

ai1e9{a_i全为1e9}

ai​全为1e9,n为

1e5{1e5}

1e5时,我们取c=1就能得到最小值。

然后我们继续分析
当c=

104{10^4}

104时,那么power sequence序列为

1104,108,1012{1,10^4,10^8,10^{12}}

1,104,108,1012
当c=

103{10^3}

103时,那么power sequence序列为

1103,106,109,1012{1,10^3,10^6,10^{9},10^{12}}

1,103,106,109,1012

很容易我们发现当c>=1000时,n不能超过4。如果超过4,我们取c=1时就能得到答案。

所以这道题我们可以枚举c。由于

ai1e9,n3{a_i≤1e9,n≥3}

ai​≤1e9,n≥3,所以

c1e9{c≤\sqrt{1e9}}

c≤1e9​。
在计算power sequence的

ai{a_i}

ai​时,如果

ai1e14{a_i≥1e14}

ai​≥1e14,就退出循环。

由于有剪枝,时间复杂度不会超。

代码

#include<iostream>
#include <sstream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
//extern "C"{void *__dso_handle=0;}
typedef long long ll;
typedef long double ld;
//typedef int fuck;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define lowbit(x) x&-x
//#define int long long

const double PI=acos(-1.0);
const double eps=1e-6;
//const ll mod=1e9+7;
const ll inf=1e18;
const int maxn=1e5+10;
const int maxm=100+10;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

ll a[maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%lld",&a[i]);
sort(a,a+n);
ll ans=inf;
for(ll c=1;c<=sqrt(1e9)+1;c++)
{
ll tmp=0,tt=1;
int flag=1;
for(int i=0;i<n;i++)
{
if(tt>=1e14) { flag=0;break;}
tmp+=abs(a[i]-tt);
tt*=c;
}
if(flag) ans=min(ans,tmp);
}
printf("%lld\n",ans);
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

[Codeforces Round #666 (Div. 2)] B. Power Sequence 暴力枚举

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » [Codeforces Round #666 (Div. 2)] B. Power Sequence 暴力枚举
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏