https://codeforces.com/contest/1111/problem/C
横坐标1..2^n对应着2^n个复仇者的基地,上面有k个复仇者(位置依次给出)。
你是灭霸你要用以下方法消灭这k个复仇者:
一开始你获取整个区间[1..2^n]
假设你当前获取的区间为[l,r]
mid = (l+r)/2
那么你每次有两种选择
1.将整个区间全都毁掉,如果这个区间里没有复仇者,那么花费为A,否则花费为B复仇者个数区间长度
2.将区间分为[l,mid]和[mid+1,r]分开毁掉(即分别获取[l,mid]和[mid+1,r]这两个区间,然后累加递归处理后的花费)
问你最小花费是多少
分析：
如果2^n比较大的话,k个复仇者其实所占据的区间会非常少
也就是说有很多区间都是空着的。。
而空着的区间其实就没有必要用第二种选择了，因为显然直接返回A是最好的 ， 越分得到的价值也越高
那问题来了 ， 我们如何很快的确定当前的区间有多少个复仇者呢？前缀和是个很好的办法 ， 但是题目数据太大，所以不可以使用这方法 ， 我们可以二分查找获取当前区间里面有多少个复仇者 ， 对记录复仇者位置的数组排序 ，然后，嘻嘻嘻
#include<bits/stdc++.h> using namespace std; #define ll long long #define INF 0x3f3f3f3f ll a[100001]; int n,k,A,B; ll dfs(ll l , ll r) { ll cnt=(r-l+1)/2; ll ans; int p=upper_bound(a+1,a+1+k,r) - lower_bound(a+1,a+1+k,l); if(p==0) return A;///不用在分了 ， 越分越小 else ans=(ll)(r-l+1)*B*p; if(r-l>=1) ans=min(ans , dfs(l,l+cnt-1) + dfs(l+cnt,r)); return ans; } int main() { scanf("%d%d%d%d",&n,&k,&A,&B); for(int i=1 ; i<=k; i++) scanf("%lld",&a[i]); sort(a+1,a+1+k); printf("%lld ",dfs(1,1<<n)); return 0; }