算法学习记录3——贪心

张开发
• 2026/4/6 22:32:39 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

算法学习记录3——贪心
核心针对最优化问题问题有关“最多最少”将一个复杂的大问题化简为几个简单的小问题分别求最优。适用题目整体最优解可以通过一系列局部最优解得到的问题。题目解题思路先计算所有卡牌的正面数值之和再计算背面与正面的数值差。将数值差从大到小排列将前k个正的数值差加在数值和里即可。代码#include bits/stdc.h using namespace std; #define ll long long const int N 1e5 10; //牌的个数 int a[N], b[N], c[N]; //牌的正面数值背面数值背面与正面的差值 ll sum 0; //牌面的数值和设置初始值为0 bool cmp(int a, int b){return a b;} //定义逆序排列的比较函数 int main() { int n, k; //最多可翻的次数 scanf(%d%d, n, k); for (int i 0;i n; i ) { scanf(%d, a[i]); sum a[i]; } for (int i 0; i n; i) scanf(%d, b[i]); for (int i 0; i n; i ) c[i] b[i] - a[i]; sort(c,cN,cmp); for(int i 0; i k; i ) { if(c[i] 0) sum c[i]; //背面与正面的差值为正值才有翻面的必要 else break; } printf(%d\n, sum); return 0; }

更多文章