B. Power Sequence(数学+枚举)Codeforces Round #666 (Div. 2)

原题链接: https://codeforces.com/contest/1397/problem/B

B. Power Sequence(数学+枚举)Codeforces Round #666 (Div. 2)
测试样例:

input
3
1 3 2
output
1
input
3
1000000000 1000000000 1000000000
output
1999982505

Note

In the first example, we first reorder {1,3,2} into {1,2,3}, then increment a2 to 4 with cost 1 to get a power sequence {1,2,4}.

题意: 给你一个整数序列,你可以先更改整数序列的顺序,之后,你可以对任意位置的元素进行+1-1操作,成本消耗为1.问变成一个等比数列的最小成本是多少?

解题思路: 这道题关键是要读懂题目。我们知道一个整数序列,同样题目中说明我们可以免费排序,那么根据等比数列的特征,我们肯定会选择从小到大排序。那么由于

ai=cia_i=c^i

ai​=ci,所以我们关键是要确定公比

cc

c,那么我们可以通过暴力枚举来解决,取成本消耗最少的值。 要注意优化时间,由于我们是不断增加公比去求成本消耗最小值,倘若我们再增加公比的值求得的成本消耗比上一次的还要高,那么这个时候我们就必须要退出了,因为之后再增加还是一样的情况。

AC代码:

/*
*邮箱:unique_powerhouse@qq.com
*blog:https://me.csdn.net/hzf0701
*注:文章若有任何问题请私信我或评论区留言,谢谢支持。
*
*/
#include<bits/stdc++.h> //POJ不支持

#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量,a为初始值,n为界限值,递增
#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量, a为初始值,n为界限值,递减。
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define mp make_pair

using namespace std;

const long long inf = 1e15;//无穷大
const int maxn = 1e5+3;//最大值。
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
//*******************************分割线,以上为自定义代码模板***************************************//

int n;
ll a[maxn];
void calculate(){
ll result=inf;
ll ans,temp;
for(ll i=1;i<=1000004;i++){
ans=a[0]-1;
temp=1;
bool flag=true;
for(ll j=1;j<n;j++){
temp*=i;
ans+=abs(a[j]-temp);
if(ans>result){
flag=false;
break;
}
}
if(!flag)break;
result=min(result,ans);
}
cout<<result<<endl;
}
int main(){
//freopen("in.txt", "r", stdin);//提交的时候要注释掉
IOS;
while(cin>>n){
rep(i,0,n-1)
cin>>a[i];
sort(a,a+n);
calculate();
}
return 0;
}

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

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

B. Power Sequence(数学+枚举)Codeforces Round #666 (Div. 2)

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

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

评论抢沙发

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

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

支付宝扫一扫打赏

微信扫一扫打赏