链接：https://ac.nowcoder.com/acm/problem/26221
来源：牛客网

题目描述

chika很喜欢吃蜜柑。每个蜜柑有一定的酸度和甜度，chika喜欢吃甜的，但不喜欢吃酸的。
一共有n个蜜柑，chika吃k个蜜柑，将获得所吃的甜度之和与酸度之和。chika想获得尽可能大的甜度总和。如果有多种方案，她希望总酸度尽可能小。
她想知道，最终的总酸度和总甜度是多少？

输入描述:

第一行有两个正整数n和k，分别代表蜜柑总数和chika吃的蜜柑数量。(1≤k≤n≤200000) 第二行有n个正整数ai，分别代表每个蜜柑的酸度。（1≤ai≤1e9） 第三行有n个正整数bi，分别代表每个蜜柑的甜度。（1≤bi≤1e9）

输出描述:

两个正整数，用空格隔开。分别表示总酸度和总甜度。

示例1

输入

3 2 1 3 4 2 2 5

输出

5 7

说明

选择1号和3号蜜柑，总酸度为5，总甜度为7，为最优解。

思路：topk问题类似，排序取大的

#include <iostream> #include <algorithm> using namespace std; const int N=2e5+10; typedef pair<int,int>PII;//<酸度，甜度> PII arr[N]; int n,k; int main() { int n,k; cin>>n>>k; for(int i = 0; i < n; i++) cin >> arr[i].first; for(int i = 0; i < n; i++) cin >> arr[i].second; sort(arr, arr + n, [&](const PII& a, const PII& b) { if(a.second != b.second) return a.second > b.second; else return a.first < b.first; }); long long s = 0, t = 0; for(int i = 0; i < k; i++) { s += arr[i].first; t += arr[i].second; } cout << s << " " << t << endl; return 0; }

知识点：

1.std::pair语法详解

template <class T1, class T2> struct pair { T1 first; // 第一个元素 T2 second; // 第二个元素 // 构造函数、赋值运算符等成员函数 };

2.sort(arr, arr + n, [&](const PII& a, const PII& b)

sort(arr, arr + n, [&](const PII& a, const PII& b) { if(a.second != b.second) return a.second > b.second; else return a.first < b.first; });

1.sort(arr, arr + n, ...)

• arr是数组起始指针

• arr + n是数组结束位置（指向最后一个元素之后）

• 第三个参数是一个比较函数，用来决定两个元素的先后顺序

2.[&]—— 捕获列表

• &表示按引用捕获所有外部变量（比如函数外的n、k等）

• 在这个 lambda 内部可以使用外部变量（尽管这里没有用到，但写[&]是允许的）

3.(const PII& a, const PII& b)—— 参数列表

• PII就是std::pair<int, int>的别名

• a和b是待比较的两个元素

• const &避免拷贝，提高效率

4. 函数体 —— 比较逻辑

if(a.second != b.second) return a.second > b.second; // 甜度不同时，甜度大的排在前面（降序） else return a.first < b.first; // 甜度相同时，酸度小的排在前面（升序）

• a.second > b.second返回true表示a应该排在b前面

• 这就是甜度降序，酸度升序的规则