27、最大的卡牌价值.docx

解题思路

这道题可以使用贪心算法和枚举来解决。

首先考虑贪心算法。对于每一副卡牌，如果将其正面朝上，则可以得到?ai?的价值。如果将其背面朝上，则可以得到?bi?的价值。如果我们将第?ii?张牌翻转可以带来的价值为?di=bi?ai。最开始卡牌已有的价值为?∑i=1nai。我们可以计算出每一副卡牌正面朝上和背面朝上的价值之差?di=bi?ai。

接下来，按照di?从大到小的顺序对卡牌进行排序。对于排序后的卡牌，我们依次考虑前?k张卡牌，当然?k?有可能大于?n。因为将同一张卡牌来回翻转是无意义的，所以?kn?时将其视为?n?即可。如果当前卡牌的?di?为正数，说明我们将其翻转后可以使得答案更大，当然di?有可能为负数，此时我们不翻转。

时间复杂度为O(nlogn)，主要因为排序操作的时间复杂度为?O(nlogn)。

AC_Code

C++

#includebits/stdc++.h

usingnamespacestd;

typedeflonglongLL;

typedefunsignedlonglonguLL;

typedefpairint,intPII;

#definepb(s)push_back(s)

#definesz(s)((int)s.size())

#definexfirst

#defineysecond

#definems(s,x)memset(s,x,sizeof(s))

#defineall(s)s.begin(),s.end()

constintinf=0x3f3f3f3f;

constintmod=1000000007;

constintN=200010;

intn,k;

intmain()

{

ios_base::sync_with_stdio(false);

cin.tie(0);cout.tie(0);

cinnk;

std::vectorinta(n),b(n),d(n);

LLans=0;

for(inti=0;in;++i){

cina[i];

ans+=a[i];

}

for(inti=0;in;++i){

cinb[i];

}

for(inti=0;in;++i)d[i]=b[i]-a[i];

sort(all(d),greaterint());

n=min(n,k);

for(inti=0;in;++i){

if(d[i]0)ans+=d[i];

}

coutans\n;

return0;

}

Java

importjava.util.*;

publicclassMain{

staticfinalintN=200010;

staticfinalintmod=1000000007;

staticfinalintinf=0x3f3f3f3f;

staticintn,k;

staticListIntegera=newArrayList();

staticListIntegerb=newArrayList();

staticListIntegerd=newArrayList();

publicstaticvoidmain(String[]args){

Scannersc=newScanner(System.in);

n=sc.nextInt();

k=sc.nextInt();

for(inti=0;in;i++){

a.add(sc.nextInt());

}

for(inti=0;in;i++){

b.add(sc.nextInt());

}

longans=0;

for(inti=0;in;i++){

ans+=a.get(i);

}

for(inti=0;in;i++){