翻倍

P12836 [蓝桥杯 2025 国 B] 翻倍

题目描述

给定 $n$ 个正整数 $A_1,A_2,\dots ,A_n$，每次操作可以选择任意一个数翻倍。

请输出让序列单调不下降，也就是每个数都不小于上一个数，最少需要操作多少次？

输入格式

输入的第一行包含一个正整数 $n$。

第二行包含 $n$ 个正整数 $A_1,A_2,\dots ,A_n$。

输出格式

输出一个整数表示需要的最小操作次数。

输入输出样例 #1

输入 #1

6
4 3 2 1 7 9

输出 #1

8

说明/提示

【样例说明】

可以将序列变为: $4,6,8,8,14,18$，总计需要 $0+1+2+3+1+1=8$ 次操作。

【评测用例规模与约定】

对于 20% 的评测用例，$n\le 10,A_i\le 100$。

对于 50% 的评测用例，$n\le 5000,A_i<2^{32}$，保证存在操作可以在所有 $A_i$ 小于 $2^{32}$ 的情况下满足题目要求。

对于 100% 的评测用例，$1\le n\le 2\times 10^5,1\le A_i<2^{32}$。

依旧写在前面

这道题赛时暴力写的，今天重新回顾一下，希望明年能拿国一。
最近在学深度学习，其实我现在看的视频从去年就开始看了…只是总是学一点就不学了，这次重新再学就是因为要做数据挖掘的大作业，感觉90%本科生做的东西就是抄网上的开源项目或者调包，自己根本不能理解其中的原理吧，反正我是不认为都能自己推理其中的数学公式然后发论文。，总结下来就是很水吧，双非学生想要保研，只需要刷那毫无含金量的绩点，参加毫无用处的科协/团委社团巴结人，随便挂个PPT大赛的名字，最难的可能就是英语六级500+了，有老师帮忙水论文更好了，总是就是无聊

思路

很容易想到一个一个遍历，然后一直*2，不过这样会超时。
然后重新寻找方法，注意到相邻两个相对大小不变，所以我们可以开一个数组cost，用来记录相邻两个之间的倍数关系。
看样例的数据4 3 2 1 7 9，索引从1开始，a[2]*2>a[i]，所以cost[2]=1，同理cost[3]=1,cost[4]=1 ，注意到a[5]>a[4]，并且a[4]*2^3<a[5],a[4]*2^4>a[5]所以cost[5]=-3,虽然a[6]>a[5]，但是a[5]*2>a[6]，所以cost[6]=0。
模拟完cost数组，我们就要进行下面的操作了，统计操作次数，如果前一个数操作了k次，那么这个数要操作k+cost[i]次，特殊的，如果k+cost[i]<=0，表示该数不用操作，并将cost[i]置为0。

代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n;
const int N=2e5+10;
int a[N];
int cost[N];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=2;i<=n;i++){
        int t=a[i];
        if(t>=a[i-1]){
            int p=a[i-1];
            int cnt=0;
            while(t>p){
                p*=2;
                cnt++;
            }
            if(p>t)
                cnt--;
            cost[i]=-cnt;
        }
        else{
            int cnt=0;
            while(t<a[i-1]){
                t*=2;
                cnt++;
            }
            cost[i]=cnt;
        }
    }
    int ans=0;
    for(int i=2;i<=n;i++){
        if(cost[i]+cost[i-1]>0){
            cost[i]+=cost[i-1];
            ans+=cost[i];
        }
        else if(cost[i]+cost[i-1]<=0){
            cost[i]=0;
        }
    }
    cout<<ans;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	solve();
	return 0;
}