专栏首页Zaqdt_ACMCodeCraft-19 and Codeforces Round #537 (Div. 2) C. Creative Snap(二分+分治)

CodeCraft-19 and Codeforces Round #537 (Div. 2) C. Creative Snap(二分+分治)

题目链接:https://codeforces.com/contest/1111/problem/C

       题意是输入n,k,a,b,表示有一个长度为2^n的区间,然后输入k个数,表示有k个超级英雄,然后输入k个超级英雄所在的位置,灭霸有两种操作,一种是删掉一个区间,如果这个区间里没有超级英雄代价就是a,如果有超级英雄代价就是这个区间长度*超级英雄个数*b,另一种操作就是将这个区间等分为[l, mid]和[mid + 1, r],问灭霸消灭所有超级英雄的最小代价是多少。

       大致思路就是按题意去模拟,用分治的思想来实现区间的等分,从而更新最小值,问题是如何判断区间内有多少个超级英雄,这里可以用二分去查找,查找区间内超级英雄的个数就是upper_bound(pre, pre + m, r) - lower_bound(pre, pre + m, l),这个长度就是区间内超级英雄的个数。


AC代码:

#include <bits/stdc++.h>
#define ll long long
#define maxn 100005
using namespace std;
int n, m, a, b;
int pre[maxn];

ll dfs(int l,int r){
  int xx = upper_bound(pre, pre + m, r) - lower_bound(pre, pre + m, l);
  if(xx == 0) return a;
  ll ans = (r - l + 1LL) * xx * b;
  int mid = (l + r) >> 1;
  if(l != r)
  ans = min(ans, dfs(l, mid) + dfs(mid + 1, r));
  return ans;
}

int main()
{
  scanf("%d%d%d%d",&n,&m,&a,&b);
  for(int i=0;i<m;i++){
    scanf("%d", &pre[i]);
  }
  sort(pre, pre + m);
  ll ans = dfs(1, 1 << n);
  printf("%lld\n", ans);
  return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Wannafly挑战赛 19 A.队列Q(思维)

    题目链接:https://www.nowcoder.com/acm/contest/131/A

    Ch_Zaqdt
  • POJ 1611 The Suspects(并查集)

           题意是爆发了SARS病毒,现在有许多个小组,只要小组里有一个人感染了病毒,那么这个小组都会有感染的嫌疑,所以让求的就是有感染嫌疑的人数,先输入n,...

    Ch_Zaqdt
  • Codeforces Round #536 (Div. 2) C. Lunar New Year and Number Division(思维)

    题目链接:http://codeforces.com/contest/1106/problem/C

    Ch_Zaqdt
  • Codeforces Round #544 (Div. 3) B. Preparation for International Women's Day(思维)

    题目链接:http://codeforces.com/contest/1133/problem/B

    Ch_Zaqdt
  • Codeforces Round #525 (Div. 2) B. Ehab and subtraction(思维)

    题目链接:http://codeforces.com/contest/1088/problem/B

    Ch_Zaqdt
  • 7-6 出生年 (15 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 【玩转腾讯云】新手小白也能漫步云端

    从我们的日常生活中可以发现,许多行业的工作流程已经转变为「无文件模式」,什么是「无文件模式」模式?其实就是各种软件、工具都开始云端化、在线化。例如...

    南风逸梦
  • 人工智能公司Next IT公司总裁Rick Collins:理解人工智能在企业中的角色

    过去几个月,机器人程序一直是在互联网上热议的话题。 微软、Facebook等科技业大公司都在向开发者开放了自己的人工智能平台。这些开放的工具和平台意味着,业界向...

    AI科技评论
  • ASP.NET生成随机验证码代码和看不清切换验证码的小结

    ============================================================

    阳光岛主
  • VS2008(C#)制作网页Tab标签切换方法(一)

    请详见本人上传的资源(AspAjax的安装与使用(内含安装文件和详细安装教程)-AJAX扩展控件,非常实用)

    阳光岛主

扫码关注云+社区

领取腾讯云代金券