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

题意 :有一个长度为\(n\)的序列,你每次可以对序列重新排序,然后花费\(1\)使某个元素加减\(1\),多次操作后使得新序列满足\(a_{i}=c^i\),\(c\)是某个正整数,求最小花费.

题解 :先排序,我们可以直接枚举\(c\),然后模拟维护一个最小值就好了.

代码 :

int n;

int a[N];

int main() {

    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	n=read();

	for(int i=1;i<=n;++i){

		a[i]=read();

	}

	ll mi=1e18;

	sort(a+1,a+1+n);

	for(int i=1;i<=100000;++i){

		ll cnt=0;

		ll tmp=1;

		for(int j=1;j<=n;++j){

			cnt+=abs(tmp-a[j]);

			if(cnt>mi) break;

			tmp*=i;

		}

		if(cnt<mi) mi=cnt;

	}

	printf("%lld\n",mi);

    return 0;

}