AcWing 4786. 闯关

目前创新互联已为成百上千家的企业提供了网站建设、域名、虚拟主机、网站托管、服务器租用、企业网站设计、旌德网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。

某综艺频道推出了一个闯关活动。

活动一共包含 n 个关卡（编号 1∼n），其中 m 个关卡为特殊关卡。

每个关卡都有一个通关分数，其中第 i 个关卡的通关分数为 ai。

挑战者可以自由决定所有关卡的具体挑战顺序，并且每通过一个关卡就可以获得该关卡的通关分数。

值得注意的是，当挑战者即将挑战的关卡是特殊关卡时，如果挑战者当前已经获得的总分数大于该特殊关卡的通关分数，则挑战者可以对该关卡的通关分数进行一次修改，修改后的新分数不能小于原分数，也不能大于挑战者当前已经获得的总分数。

请你计算并输出挑战者通过所有关卡获得的总分数的大可能值。

输入格式
第一行包含两个整数 n,m。

第二行包含 n 个整数 a1,a2,…,an，表示每个关卡的通过分数。

第三行包含 m 个整数 b1,b2,…,bm，表示每个特殊关卡的编号。

输出格式
一个整数，表示挑战者通过所有关卡获得的总分数的大可能值。

保证最终答案不超过 264−1。

数据范围
前 4 个测试点满足 1≤n≤4。
所有测试点满足 1≤n,m≤100，m≤min(n,30)，1≤ai≤107，1≤bi≤n，bi 两两不同。

输入样例1：

4 1
1 3 7 5
3

输出样例1：

18

输入样例2：

3 2
10 3 8
2 3

输出样例2：

40

输入样例3：

2 2
100 200
1 2

输出样例3：

400

输入样例4：

1 1
1
1

输出样例4：

1

题意：

• 题意：一共n个关卡，m个特殊关卡，挑战者可以自由选择挑战关卡
• 挑战特殊关卡时，如果挑战者当前分数大于当前关卡，挑战者可以修改当前关卡的分数，
• 修改要求为 分数大于原来关卡，但小于当前分数
• 求挑战者可能获取的最高分

题解：

• 代码解释
  首先用数组a记录各个关卡分数，数组b记录特殊关卡分数，布尔数组st记录是否为特殊关卡
  思路：先将非特殊关卡相加，再将特殊关卡数组从大到小排序（以获取总分数的大值）

代码：

#include#include#include 

using namespace std;

typedef long long LL;

const int N = 110;
LL a[N],b[N];
bool st[N];

LL n,m;
LL res = 0;

int main()
{cin >>n >>m;
    for(int i = 1;i<= n;i++) 
    {cin >>a[i];
        st[i] = true;
    }
    
    for(int i = 1;i<= m;i++)
    {int x;
        cin >>x;
        st[x] = false;      // 记录该关卡为特殊关卡
        b[i] = a[x];        // 将该关卡的分数存到数组b中
    }
    
    sort(b + 1, b + m + 1, greater());  // 从大到小排序特殊关卡
    
    for(int i = 1;i<= n;i++) 
    {if(st[i]) res += a[i];      // 先将非特殊关卡的分数相加
    }
    
    if(m == n)         // 若全部为特殊关卡
    {res = b[1];    
        for(int i = 2;i<= m;i++) res = res * 2;  // 由于数组b倒序，所有后面的关卡分数都可以调为分数总和
    }
    else
    {for(int i = 1;i<= m;i++)
        {if(res< b[i]) res = res + b[i];  // 存在特殊关卡的分数大于当前分数总和，则直接加上该关卡
            else res = res * 2;
        }
    }
    
    cout<< res<< endl;   // 输出可能获得的大分数

    return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

当前名称：AcWing4786.闯关-创新互联
网页路径：http://kswjz.com/article/ddcdjs.html