B. Power Sequence
题意
给出一个数组a 长度为n<1e5 任意元素ai<1e9
要求通过两步操作：
1.交换其中元素的位置，不产生花费
2.使其中某个元素+1or-1 这个操作每次产生1个花费
将它变成新的序列满足 第i项为 $c^i$ (i从0开始)最少花费是多少
题解
想让操作次数最少 首先想到的是将数组a升序排列最优
其次想到c的上界满足 $c^{n-1}$大于等于$a_n$ 的最小的c
所以我们二分c的上界, 此处我们不用“乘” 来check $c^{n-1} > a_n$
而用“除” 来check $a_n/=c$ 需要几次才能除完即$a_n$ 是c的几次幂 因为乘会爆ll,
求得c的上界然后枚举c 更新最优解
这里需要注意：$c^i$ 或$∑(a_i-c^i)$ 可能爆ll 结果会导致小于0
wa4 输出结果尽然比正确答案小 想不明白。。。
第4个测试点n=100 按理说c=1 所以答案=$∑abs(a_i-c^{i-1})$ 怎么的也不会溢出。。
猜测c=1的答案被其他c(用骚操作看到c=2) 错误更新了虽然$c^i$没溢出 (明明2的62次会溢出)
但是$∑(a_i-c^i)$ 溢出了
1
2
3
4
5
6
7
| ll pi=1;
for(int i=0;i<=100;i++){
pi*=2;
if(pi<=0)break;
cout<<pi<<endl;
}
|
(由于二分了c的上界,$c^i$并不会溢出)
当出现这种情况表示已经可以break了因为最后不会超过上限
假如$c^{n-1}>a_n$ 那么有 $abs(c^{n-1}-a_n) ≈ 1e9$ 的量级
而$abs(c^{i-1}-a_i)$不超过$abs(c^{n-1}-a_n)$的量级
溢出则说明肯定不是最优解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e5+5;
const double Pi=acos(-1);
const ll Mod=1e9+7;
ll data[Max],n;
bool check(int c,int num){
int cnt=0;
while(num){
num/=c;
cnt++;
}
return cnt<=n-1;
}
int main() {
Turnoff;
cin>>n;
for(int i=0;i<n;i++)cin>>data[i];
sort(data,data+n);
int L=2,R=100000,c=1;
while(R>L){
int mid=(L+R)>>1;
if(check(mid,data[n-1])){
c=mid;
R=mid-1;
}
else L=mid+1;
}
ll ans=2e18;
for(ll p=1;p<=c;p++){
ll temp=1,need=0,per=0;bool flag=0;
for(int i=0;i<n;i++){
need+=abs(data[i]-temp);
temp*=p;
if(temp<=0||per>need){
flag=1;
break;
}
per=need;
}
if(flag)break;
ans=min(ans,need);
}
cout<<ans<<endl;
}
|
参考其他博客的代码，感觉剪枝的更合理的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <cstdio>
#include <algorithm>
using namespace std;
long long i,n,c,cnt,ans,C,a[100005];
int main(){
scanf("%lld",&n);
ans=-n;
for (i=1; i<=n; i++) scanf("%lld",&a[i]),ans+=a[i];
sort(a+1,a+n+1);
for (c=1; c<=1000000; c++){
cnt=0;
for (i=1,C=1; i<=n; i++,C*=c){
if (C>a[i]) cnt+=C-a[i]; else cnt+=a[i]-C;
if (cnt>=ans) break;
}
if (cnt<ans) ans=cnt;
}
printf("%lld",ans);
}
|