题面：

题目描述：

灭霸想要摧毁复仇者联盟的基地。基地的长度为2的n次方，基地可以看成是一个长度为2的n次方的数组。基地的每一个位置可以由很多个超级英雄，但是一个超级英雄只能站一个位置。灭霸想用最小的力量摧毁复仇者联盟的基地。从破坏一整个基地开始，每一步他可以执行其中一项操作：

1.如果当前基地长度大于等于2，那么灭霸可以把基地分开成两半。

2.烧掉当前基地。如果当前基地没有任何超级英雄，则需要A的力量。否则，灭霸需要B*num*l的力量。其中num是当前基地的超级英雄数量，l是当前基地的长度。

问：灭霸所需要的最小力量是多少？

题目分析：

这道题先要读懂题意：对于每次操作，可以选择直接破坏（燃烧）当前基地，或者把基地分成两半再进行破坏。

1.题意理解：

刚开始，基地是连成一体的：

灭霸可以直接把整个基地破坏，其中需要用B*3*8的力量，这时，整个基地就被破坏完了。

但是，我们也可以这样：不把整个基地直接破坏，先分成两半：

再分别破坏两个基地。或者，继续分成两半（这时有三种方案）：

再分别破坏它们。或者，再分成两半......

这里要注意的是：如果一个基地一个英雄都没有，就直接用A的力量破坏掉，而不是尝试分半后再继续破坏。

2.很容易发现，其实这个就类似于归并排序（递归？dfs？分治？二分？？？）的做法就可以完成这道题了。在找某个区间有多少个超级英雄时要用二分去找，不然会超时。

3.我们可以写一个dfs的函数，传入1和2^n（也就是传入区间[1, 2^n]）。然后，我们在dfs函数里面尝试对这个区间分半和不分半的操作：如果不分半，就直接计算结果：计算当前区间里面有多少个英雄。如果没有英雄，dfs函数就直接返回这个区间要A的力量。如果有英雄，就用二分的方法（先要把英雄站的位置排好序）或者用upper_bound,lower_bound，算出当前区间的英雄个数，然后算出要花费的力量，再计算这个区间如果分半后（用递归分半）的需要花费的力量（大小就是dfs(l, mid)+dfs(mid+1, r)，其中mid = (l+r)/2 ），取两者的最小值，然后再返回就行了。

4.坑：二分容易弄错，数据没有开long long.

AC代码：

 1 #include <cstdio>

 2 #include <cstring>

 3 #include <iostream>

 4 #include <cmath>

 5 #include <algorithm>

 6 using namespace std;

 7 const int maxn = 1e5+5;

 8 long long n, k, A, B;

 9 long long a[maxn];

10

11 long long binary(long long x){   //二分，左开右闭的设置

12     long long l = 0, r = k+1;

13     long long mid;

14     while(l < r){

15         mid = (l+r)/2;  //左开右闭向下取整

16         if(a[mid] < x) l = mid+1;

17         else r = mid;

18     }

19     return l;

20 }

21

22 long long dfs(long long l, long long r){

23     int num = binary(r+1)-binary(l);  //计算出位置区间[l, r]内的英雄个数

24

25     long long res;

26     if(!num) return A;

27     else res = B*num*(r-l+1);

28

29     if(l == r) return res;  //递归终点

30     else return min(res, dfs(l, (l+r)/2)+dfs((l+r)/2+1, r));  //取小的作为结果

31 }

32

33 int main(){

34     cin >> n >> k >> A >> B;

35     for(int i = 1; i <= k; i++){

36         scanf("%lld", &a[i]);

37     }

38     sort(a+1, a+k+1);

39

40     //为了方便用二分而设置的

41     a[k+1] = 2e9;

42

43     long long r = (1<<n);

44

45     cout << dfs(1, r) << endl;

46     return 0;

47 }

巴特西

Codeforces Round #537 C. Creative Snap

题面：

题目描述：

题目分析：

最新文章

热门文章