1.合并果子P1090 思路：每次将最小的两个果堆合并成一个新堆，合并后排序，但是超时了#include<bits/stdc++.h> using namespace std; int a[20000]; int main() {int n,i,cnt=0,r=1,nn;cin>>n;nn=n;for(i=1;i<=n;i++)cin>>a[i];for(;;){sort(a+r,a+n+1);cnt+=a[r]+a[r+1];a[r+1]=a[r]+a[r+1];r++;nn--;if(nn==1)break;}cout<<cnt;return 0; }优化代码 法1.使用优先队列或二叉树，可以高效地找出集合中的最小值，目前还未学习 法2.
本文仅供学习参考使用，谢谢 目录：问题描述：算法思想：测试数据：代码： 问题描述： Alice和Bob穿越成了加勒比的海盗。有一次海盗们发现了一个大的宝藏，金币总额M的位数比海盗们的人数还多!他们靠决斗产生了海盗的排位，并约定，无论面对的金币数量是多少，都需要在这个数目的基础上划掉位作为给下一个海盗的数目。每个海盗都希望自己拿到的金币数量最多，井假设他们都是聪明的；都知道要怎么做才能保证自己拿到最多的金币。Bob...
题目： 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 示例 1: 输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格...
题意： 数轴上有 n个闭区间 [ai, bi]，选择尽量少的区间覆盖一条指定线段 [1, t]，不可能办到输出-1。 思路： 定义一个结构体代表区间，在读入数据后，对数据进行多关键字排序（第一是左端点小的在前，第二是右端点大的在前）。对数据进行过滤，左端点相同的区间只保留区间长度最大的，如果当前区间被之前保留的区间完全包含则去掉。 如果数组中第一个区间不包含1即不可能包含[1,t]，直接返回-1。 定义一个变量point表示将需要覆盖...
贪心算法 1. 拼接字符串使字典序最小 比如：“ab”、“cd”、"ef"三个字符串，拼接的结果可以有多种，但是”abcdef“这个结果才是最小的。 1.1 分析：按单个字符串的字典序进行比较：比如a小于b，则a放b前面 这种思路是错误的：比如b和ba，字典序肯定是b小，但拼接的时候应该ba放前面，因为结果bab最小两个字符串拼接之后再比较，看谁放前面比较合适：比如a和b，看ab和ba哪个更小对于第二种思路，就是一种贪心策略，该策略具有传递...
基本思想： 想到贪心，但是觉得时间复杂度太高，结果一不小心写出来个更复杂的贪心； 关键点： 注意特殊用例，有可能无法遍历出正确结果，即没有切换得到正确的值，此时要避免进入死循环； #include<iostream> #include<vector> #include<algorithm> #include<string> #include<cmath> #include<set> using namespace std;const int maxn = 5010; int n,m; int dp[maxn][maxn];vector<string>v1; vector<string>v2;int main() {...
已知一些孩子和一些糖果，每个孩子有需求因子g，每个糖果有大小s, 当某个糖果的大小s>=某个孩子的需求因子g时，代表该糖果可以满足孩子；求使用这些糖果，最多能满足多少孩子？ （某个孩子只能用1个糖果满足） 例如：需求因子组g=[5,10,2,9,15,9];糖果大小数组s=[6,1,20,3,8];最多可以满足3个孩子。 #include<vector> #include<algorithm> class Solution { public:Solution(){}~Solution(){}int findContentChildren(std::vector<...
这题和我之前做的https://www.cnblogs.com/Jun10ng/p/12363679.html 是同一个题目，但是现在多了一个条件 1<=n<=1000 如果还是用dp的话，dp数组就要用大数类BigInteger 但是，还有一种解法，贪心算法 题目 同上 思路 原本打算用大数类的dp数组 但是看了下贪心的解法，也很容易理解 就是一直乘3， 收获 大数类的使用 头文件是 java.math.BigInteger 初始化函数是BigInteger（String类的数字） 代码（贪心） class Solution {public ...
题目描述 Tom最近在研究一个有趣的排序问题。如图所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。操作a 如果输入序列不为空，将第一个元素压入栈S1 操作b 如果栈S1不为空，将S1栈顶元素弹出至输出序列 操作c 如果输入序列不为空，将第一个元素压入栈S2 操作d 如果栈S2不为空，将S2栈顶元素弹出至输出序列 如果一个1~n的排列P可以通过一系列操作使得输出序列为1，2，…，(n-1)，n，Tom就称P是一个“可双栈排...
基本思路： 和之前一题类似，只不过算的是总体等待时间； 关键点： 无； #include<iostream> #include<stdlib.h> #include<stdio.h> #include<vector> #include<string> #include<math.h> #include<algorithm> #include<cstring> #include<map> #include<queue> #include<set> #include<stack> using namespace std; int m, n; vector<int>peo; vector<vector<int>>t;void charge() {for (int i = 0; i < peo.size(); i++) {t[...
一、贪心算法的定义 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。 二、基本思想 贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根...
前情提要 有n个活动(假设n很大，人力安排较困难) n个活动的开始时间和结束时间已经知道 但我又想充分利用资源，安排最多数量的活动 贪心算法 语言：python 可视化依赖的第三方库：numpy,matplotlib 开始活动安排之旅 贪心算法概述： 创建活动类（或结构体）,按照用户输入实例化为一个个活动对象,按照活动的结束时间增序对活 动整体排序，挑选活动时，活动的结束最早的优先被选取，为剩下活动留下最多的时间来安排（每次使剩下的...
贪心算法 贪心算法问题解决步骤第一步，当我们看到这类问题的时候，首先要联想到贪心算法：针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。 第二步，我们尝试看下这个问题是否可以用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。 第三步，我们举几个例子看下贪心算法产生的结果是否是最优的。贪心算法实战分析分糖果：有 m 个糖...
#include <iostream> #include <algorithm>using namespace std;// 贪心法 // 最优装载问题 void optionalLoad(int *a, int n, int C) {sort(a, a + n);int retain = C;for (int i = 0; i < n; i++) {if (a[i] <= retain) {cout << a[i] << " ";retain -= a[i];}}cout << endl; }int main() {while (true) {// n个物体int n;cout << "请输入物体总数(0退出)：";cin >> n;if (!n) {break;}int C;cout << "请输入不超过的总重量：";c...
题目核心代码流程图遇到的困难及解决办法 最开始考虑这道题的时候是想将s数组里的数慢慢相加 每当和>=100时 便清零并且重新设置一个容量为100的箱子 继续存储 结果编译起来十分困难。 后来逆向思维 先构造一定数量的容量均为100的一维数组box[] 然后存放 用容量减去s数组里的元素 每当容量即将<=0时 便开始使用下一个box中的元素进行计算。 面对思路较为清晰 但编译较为麻烦时 可以逆转思维 减少编译时遇到的困难。