题目描述 0.5s 512MB
小明是某个游戏中粮仓的管理者，粮食在过冬的时候被老鼠吃掉了好多，因此对不上账了。可是马上领导就要来检查了，小明很慌张。
粮仓里面一共有\(n\)堆粮食，第\(i\)堆粮食按账目上的数量，应该有\(a_i\)斤。
但是现在每一堆粮食都只剩下\(1\)斤了。
于是小明决定祭出自己的终极武器：粮食放大器。
具体地：小明每次可以使用一个从付费商城购买的粮食放大器，然后对区间\([l,r]\)使用，使用后，区间\([l,r]\)里的每一堆粮食，要么\(+1\)斤，要么\(\times 2\)，这个小明可以自主决定（也就是，每一堆可以自主的选择\(+1\)或者\(\times 2\)）。
由于粮食放大器很贵，所以小明决定尽量少的购买粮食放大器。
请帮助小明算一下，他最少要购买多少个粮食放大器，才能完成目标。
请注意，小明必须把每一堆粮食恰好变成\(a_i\)。
输入格式
第一行输入\(n\)。
第二行输入\(n\)个正整数，表示\(a_1,...,a_n\)。
输出格式
输出答案在单独的一行。
样例输入 #1
1
101
样例输出 #1
9
样例输入 #2
3
3 2 3
样例输出 #2
3
样例输入 #3
10
3 1 3 100 13 2 14 3 5 14
样例输出 #3
17
数据范围
对于10%的数据：\(n\leq 1,a_i\leq 10^6\)。
对于25%的数据：\(n\leq 1\)。
对于60%的数据：\(n\leq 50000\)。
对于70%的数据：\(n\leq 10^5\)。
对于80%的数据：\(n\leq 2\times 10^5\)。
对于100%的数据：\(1\leq n\leq 10^6,1\leq a_i\leq 10^{18}\)。
analysis:
求出每个数字的最大次数和最小次数，让他们尽可能接近，画图可以分析出来，如果前面的数字确定下来是x次，下一个数字如果上下界如果包含x，则当前数字的次数也是x,如果不包含，下界大于x，则取下界，上界小于x，则取上界。
obstacle：当前数字区间和前一个数字区间做比较，就傻了，应该和前一个已经确定的数字x做比较。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,b[2000005], ans;
int cal(ll x){
ll cnt = 0;
while(x > 1){
cnt++;
if(x & 1 == 1) x -= 1;
else x >>= 1;
}
return cnt;
}
struct Node{
ll l, r;
}a[2000005];
int main(){
cin>>n; ll x;
for(int i = 1; i <= n; i++){
cin>>x;
a[i].r = x-1;
a[i].l = cal(x);
// cout<<"pp: "<<i<<" "<<a[i].l<<" "<<a[i].r<<endl;
}
if(n == 1) {
cout<< a[1].l;
return 0;
}
if(a[2].l >= a[1].r){
b[2] = a[2].l, b[1] = a[1].r;
}
else if(a[2].r < a[1].l){
b[2] = a[2].r, b[1] = a[1].l;
}
else if(a[2].r <= a[1].r)
b[2] = a[2].r, b[1] = a[2].r;
else if(a[2].l >= a[1].l)
b[2] = a[2].l, b[1] = a[2].l;
// cout<<"b: "<<b[1]<<" "<<b[2]<<endl;
for(int i = 3; i <= n; i++){
if(a[i].l <= b[i-1] && a[i].r >= b[i-1])
b[i] = b[i-1];
else if(a[i].l > b[i-1])
b[i] = a[i].l;
else if(a[i].r < b[i-1])
b[i] = a[i].r;
}
// cout<<"b: "<<b[3]<<endl;
for(int i = 1; i <= n; i++){
ll y = b[i] - b[i-1];
if(y > 0) ans += y;
}
cout<<ans<<endl;
return 0;
}