给 n 个关卡,每个关卡得分为 ai,有 m 次机会可以选择一
个关卡通过后不得分,而将现有得分翻倍
你可以安排关卡的通过顺序和策略,求最大得分.
看到这道题首先想到的就是贪心,贪心不仅是最好想也是最好写的。
知道这些了以后,我们可以写代码了
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 1000010
using namespace std;
long long n,m,a[maxn],b[maxn],c[maxn],cnt,ans;
int cmp(int x,int y){
return x>y;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
ans+=a[i];
}
for(int i=1;i<=m;i++){
cin>>b[i];
for(int j=1;j<=n;j++){
if(b[i]==j){
c[j]=a[b[i]];
ans-=a[b[i]];
cnt++;
}
}
}
sort(c+1,c+n+1,cmp);
for(int i=1;i<=cnt;i++){
if(ans*2>=ans+c[i]) ans*=2;
else ans+=c[i];
}
cout<<ans;
return 0;
}
制作不易,若有错请各位指正
原文:https://www.cnblogs.com/KnightL/p/13935445.html