网站建设与客户价格谈判技巧,开发网站开票名称是什么,厦门网站制作企业,网站生成word目录 引言一、合并果子#xff08;Huffman树#xff09;二、排队打水#xff08;排序不等式#xff09;三、货仓选址#xff08;绝对值不等式#xff09;四、耍杂技的牛#xff08;推公式#xff09; 引言
上一篇文章也说过了这个贪心问题没有一个规范的套路和模板Huffman树二、排队打水排序不等式三、货仓选址绝对值不等式四、耍杂技的牛推公式 引言
上一篇文章也说过了这个贪心问题没有一个规范的套路和模板主要还是因题而异到了考场上基本是靠猜所以本篇文章主要还是以讲题为主。 一、合并果子Huffman树
思路这道题其实是道Huffman的问题就是怎么让体力值最小那么肯定是最开始从最小的合并因为刚开始合并成一堆又因为最后要合并成一堆相当于以前的会再次移动一次所以肯定前面合并的要移动的次数肯定是会比后面移动的次数多的所以先把移动小的当然要更优。
题目描述
在一个果园里达达已经将所有的果子打了下来而且按果子的不同种类分成了不同的堆。达达决定把所有的果子合成一堆。每一次合并达达可以把两堆果子合并到一起消耗的体力等于两堆果子的重量之和。可以看出所有的果子经过 n−1 次合并之后就只剩下一堆了。达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家所以达达在合并果子时要尽可能地节省体力。假定每个果子重量都为 1并且已知果子的种类数和每种果子的数目你的任务是设计出合并的次序方案使达达耗费的体
力最少并输出这个最小的体力耗费值。例如有 3 种果子数目依次为 129。可以先将 1、2 堆合并新堆数目为 3耗费体力为 3。接着将新堆与原先的第三堆合并又得到新的堆数目为 12耗费体力为 12。所以达达总共耗费体力31215。可以证明 15 为最小的体力耗费值。输入格式
输入包括两行第一行是一个整数 n表示果子的种类数。
第二行包含 n 个整数用空格分隔第 i 个整数 ai 是第 i 种果子的数目。输出格式
输出包括一行这一行只包含一个整数也就是最小的体力耗费值。
输入数据保证这个值小于 231。数据范围
1≤n≤10000,1≤ai≤20000
输入样例
3
1 2 9
输出样例
15示例代码
#include cstdio
#include iostream
#include algorithm
#include vector
#include queueusing namespace std;typedef long long LL;const int N 1e510;int n;int main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);priority_queueint, vectorint, greaterint heap;cin n;for(int i 0; i n; i){int t;cin t;heap.push(t);}LL res 0;while(heap.size() 1){int a heap.top(); heap.pop();int b heap.top(); heap.pop();res a b;heap.push(ab);}cout res endl;return 0;
}二、排队打水排序不等式
思路要让总的等待时间最短那么肯定是让时间最长的人靠后短的靠前排个序就行了。
题目描述
有 n 个人排队到 1 个水龙头处打水第 i 个人装满水桶所需的时间是 ti请问如何安排他们的打水顺序才能使所有人的等待时间之和最小输入格式
第一行包含整数 n。
第二行包含 n 个整数其中第 i 个整数表示第 i 个人装满水桶所花费的时间 ti。输出格式
输出一个整数表示最小的等待时间之和。数据范围
1≤n≤105,1≤ti≤104
输入样例
7
3 6 1 4 2 5 7
输出样例
56示例代码
#include cstdio
#include iostream
#include algorithmusing namespace std;typedef long long LL;const int N 1e510;int n;
int a[N];int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n;for(int i 1; i n; i) cin a[i];sort(a1, an1);LL res 0;for(int i 1; i n; i){res a[i] * (n - i);}cout res endl;return 0;
}三、货仓选址绝对值不等式
思路由下图可知选在中心点的位置是最好的如果货仓是偶数的话选在 [ a , b ] [a,b] [a,b]中的任意一点的结果都是一样的。
题目描述
在一条数轴上有 N 家商店它们的坐标分别为 A1∼AN。现在需要在数轴上建立一家货仓每天清晨从货仓到每家商店都要运送一车商品。为了提高效率求把货仓建在何处可以使得货仓到每家商店的距离之和最小。输入格式
第一行输入整数 N。
第二行 N 个整数 A1∼AN。输出格式
输出一个整数表示距离之和的最小值。数据范围
1≤N≤100000,0≤Ai≤40000
输入样例
4
6 2 9 1
输出样例
12示例代码
#include cstdio
#include iostream
#include algorithm
#include cmathusing namespace std;typedef long long LL;const int N 1e510;int n;
int a[N];int main()
{cin n;for(int i 0; i n; i) cin a[i];sort(a, an);int md a[n1];LL res 0;for(int i 0; i n; i){res abs(a[i] - md);}cout res endl;return 0;
}四、耍杂技的牛推公式
思路这个其实也就是从小到大排序就是最优解了也没什么为什么能证出来记住就行了。
题目描述
农民约翰的 N 头奶牛编号为 1..N计划逃跑并加入马戏团为此它们决定练习表演杂技。奶牛们不是非常有创意只提出了一个杂技表演
叠罗汉表演时奶牛们站在彼此的身上形成一个高高的垂直堆叠。
奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。这 N 头奶牛中的每一头都有着自己的重量 Wi 以及自己的强壮程度 Si。一头牛支撑不住的可能性取决于它头上所有牛的总重量不包括它自己减去它的身体强壮程度的值现在称该数值为风险值
风险值越大这只牛撑不住的可能性越高。您的任务是确定奶牛的排序使得所有奶牛的风险值中的最大值尽可能的小。输入格式
第一行输入整数 N表示奶牛数量。
接下来 N 行每行输入两个整数表示牛的重量和强壮程度第 i 行表示第 i 头牛的重量 Wi 以及它的强壮程度 Si。输出格式
输出一个整数表示最大风险值的最小可能值。数据范围
1≤N≤50000,1≤Wi≤10,000,1≤Si≤1,000,000,000
输入样例
3
10 3
2 5
3 3
输出样例
2示例代码
#include cstdio
#include iostream
#include algorithmusing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondconst int N 1e510;int n;
PII cow[N];int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n;for(int i 0; i n; i){int w, s;cin w s;cow[i] {ws, w};}sort(cow, cown);LL res -2e9, sum 0;for(int i 0; i n; i){int w cow[i].y, s cow[i].x - w;res max(res, sum - s);sum w;}cout res endl;return 0;
}
