Creative Snap

Thanos wants to destroy the avengers base, but he needs to destroy the avengers along with their base.

Let we represent their base with an array, where each position can be occupied by many avengers, but one avenger can occupy only one position. Length of their base is a perfect power of 22. Thanos wants to destroy the base using minimum power. He starts with the whole base and in one step he can do either of following:

• if the current length is at least 22, divide the base into 22 equal halves and destroy them separately, or
• burn the current base. If it contains no avenger in it, it takes AA amount of power, otherwise it takes his B⋅na⋅lB⋅na⋅l amount of power, where nana is the number of avengers and ll is the length of the current base.

Output the minimum power needed by Thanos to destroy the avengers' base.

点击传送到​​原题​​

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#define mem(a,x) memset(a,x,sizeof(a))
#define s1(x) scanf("%d",&x)
#define s2(x,y) scanf("%d%d",&x,&y)
#define s3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define s4(x,y,z,k) scanf("%d%d%d%d",&x,&y,&z,&k)
#define ls 2*rt
#define rs 2*rt+1
#define lson ls,L,mid
#define rson rs,mid+1,R
#define ll long long
using namespace std;
typedef pair<int,int> pii;
//inline ll ask(int x){ll res=0;while(x)res+=c[x],x-=x&(-x);return res;}
//inline void add(int x,int d){while(x<=n)c[x]+=d,x+=x&(-x);}
//int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b);}
const ll inf = 0x3f3f3f3f;
const int mx = 1e5+10;
int n,k,A,B;
int num[mx]; 
ll fun(ll l, ll r){

  int i = lower_bound(num,num+k,l)-num;
  int j = upper_bound(num,num+k,r)-num;
  if(i == j ) return A;
  ll p,q;
  p=1LL*B*(j-i)*(r-l+1);
  if(l==r){
    return p;
  }
  
  ll mid  = (l+r)/2;
  q =  fun(l,mid)+fun(mid+1,r);
//  printf("l=%d, r = %d  ans =%d\n",l,r,min(p,q));
  return min(p,q);
}
int main(){
  //freopen("C:\\Users\\black\\Desktop\\in.txt","r",stdin);
  //int T=10; scanf("%d",&T);
  scanf("%d%d%d%d",&n,&k,&A,&B);
  //int tot = 0
  for(int i = 0; i < k ;i++){
    s1(num[i]);  
  }
  sort(num,num+k);
  cout<<fun(1,1<<n);


  return 0;
}