蓝桥杯备考冲刺必刷题（C++） | 3250 最大的卡牌价值

学习C++从娃娃抓起！记录下蓝桥杯备考比赛学习过程中的题目，记录每一个瞬间。

附上汇总贴：蓝桥杯备考冲刺必刷题（C++） | 汇总-CSDN博客

【题目描述】
给定 n n n副卡牌，每张卡牌具有正反面，正面朝上数字为 a i a_i ai​，背面朝上数字为 b i b_i bi​。一副卡牌的价值为正面朝上数字之和。一开始所有卡牌都是正面朝上的。小蓝是蓝桥学院最优秀的魔法师，他知道所有卡牌的背面数字 b i b_i bi​，他最多可以进行 k k k次操作，每次可以将一副卡牌翻转，将正面朝上的数字变为背面朝上的数字，或将背面朝上的数字变为正面朝上的数字。请问，小蓝最多可以使卡牌的价值之和为多少?
【输入】
第一行输入两个整数 n n n和 k k k，表示卡牌的数量和小蓝可以操作的次数。
第二行输入 n n n个整数 a i a_i ai​，表示所有卡牌正面的数字。
第三行输入 n n n个整数 b i b_i bi​，表示所有卡牌反面的数字。
【输出】
输出一个整数，表示可以得到的卡牌的最大价值和。
【输入样例】

3 1
1 2 3
3 2 1

【输出样例】

8

【代码详解】

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, k, ans, maxn=-1e9;
struct node {
    int a, b, c;
}p[100005];
bool cmp(node x, node y) 
{
    return x.c > y.c;
}
signed main()
{
    cin >> n >> k;
    for (int i=1; i<=n; i++) {  // 输入卡牌正面数字
        cin >> p[i].a;
        ans += p[i].a;  // 计算正面卡牌价值总和
    }
    for (int i=1; i<=n; i++) {  // 输入卡牌背面数字
        cin >> p[i].b;
        p[i].c = p[i].b - p[i].a;  // 计算背面与正面的数字差
    }
    sort(p+1, p+n+1, cmp);  // 按照数字差的从大到小排序
    for (int i=1; i<=min(k, n); i++) {  // 贪心策略，优先考虑反转数字差较大的卡牌
        ans -= p[i].a;
        ans += p[i].b;
        maxn = max(maxn, ans);  // 每翻一张牌比较下最大值
    }
    cout << maxn << endl;  // 输出最大值和
    return 0;
}

【运行结果】

3 1
1 2 3
3 2 1
8