微云做网站,电商网站建设目的,建设工程教育网app,绍兴百度seo公司导引#xff08;硕鼠的交易#xff09;
硕鼠准备了M磅猫粮与看守仓库的猫交易奶酪。
仓库有N个房间#xff0c;第i个房间有 J[i] 磅奶酪并需要 F[i] 磅猫粮交换#xff0c;硕鼠可以按比例来交换#xff0c;不必交换所有的奶酪
计算硕鼠最多能得到多少磅奶酪。
输入M和…导引硕鼠的交易
硕鼠准备了M磅猫粮与看守仓库的猫交易奶酪。
仓库有N个房间第i个房间有 J[i] 磅奶酪并需要 F[i] 磅猫粮交换硕鼠可以按比例来交换不必交换所有的奶酪
计算硕鼠最多能得到多少磅奶酪。
输入M和N表示猫粮数量和房间数量随后输入N个房间每个房间包括奶酪数和猫粮数
Input 5 37 24 35 2-1 -1
Output 13.333
解法计算每个房间的奶酪与猫粮之比比值越大硕鼠收益越高将所有比值从大到小排序最后选择比值大的即可。 例1田忌赛马
问题描述田忌与齐王赛马每匹马的速度不同。
目标赢得最多的比赛。
策略利用田忌的最弱的马去对齐王的最强的马反之亦然。
不要固定认为是将田忌第一强的马与齐王第二强的马进行比较因为可能田忌第一强的马比齐王第一强的马更强 经典贪心事件序列问题 命题至少存在一个最长的事件序列包含最早结束的事件
采用反证法证明假设有一个最长的事件序列bcdef不包含最早结束的事件a显然a在b之前结束那么事件序列acdef依旧是最短事件序列。
显然选中最早结束的事件对最长的事件序列无影响。
那么我们可以选中最早结束的事件0然后再选中发生时刻大于等于3且结束时刻最小的事件
继续选中事件1然后再选中发生时刻大于等于4且结束时刻最小的事件
继续选中事件5然后再选中发生时刻大于等于10且结束时刻最小的事件
继续选中事件8然后再选中发生时刻大于等于15且结束时刻最小的事件
继续选中事件10然后发现没有可选事件了最长事件序列为0,1,5,8,10
贪心思路先把所有事件按结束时刻从大到小排序随后每次选择一个最早结束且和之前不冲突的事件
例2搬桌子 一层楼的布局如上现在需要将一些桌子从一个房间搬到另一个房间。无论距离远近每趟搬运都需要十分钟。
当你从房间 i 搬桌子到房间 j 时房间 i 到房间 j 的走廊被占用也就是同一时间的走廊是互斥的。
现在需要计算完成所有搬运任务最少需要多长时间。
输出包含T组用例。首先输入一个正整数N表示需要搬运的桌子数接下来N行每行包含2个正整数a和b表示需要将桌子从a房间搬到b房间
输出为每组用例搬运任务需要的最少时间。
思路记录每段区间的走廊被占用的次数重合的次数就是需要搬运的次数 #includeiostreamusing namespace std;int t, i, j, N, P[200]; int s, d, temp, k, MAX;int main(){cin t;for(i 0; i t; i){// 初始化 for(j 0; j 200; j){P[j] 0;}cin N;for(j 0; j N; j){cin s d;s (s-1)/2;d (d-1)/2;if(s d){swap(s, d);}for(k s; k d; k){P[k];}}MAX -1;for(j 0; j 200; j){MAX max(MAX, P[j]);}cout MAX*10 endl;}return 0;} 例3删数问题 思路显然高位越小越好。每次比较相邻两数若左边比右边大则删去左边的数否则继续比较后面的数。 例4青蛙的邻居 输入t组样例每组样例先输入n个湖泊每个青蛙呆在不同湖泊里面然后输入n青蛙的邻居个数问能否根据这些数据构成一个图。
问题本质可图性判断
1、度序列若把图G所有顶点的度数排成一个序列S则称S为图G的度序列。
2、序列是可图的一个非负整数组成的有限序列如果是某个无向图的度序列则称该序列是可图的。
算法Havel-Hakimi定理
由非负整数组成的非增序列Sd1 , d2, ... dn(n 2, d1 1)是可图的当且仅当序列S1d2-1, d3-1, ..., dd11-1, dd12, ... ,dn是可图的。
其中序列S1中有n-1个非负整数S序列中d1后的前d1个度数(即d2 ~ dd11)减 1 后构成S1中的前d1个数。
通俗理解
假设有一群人的邻居数为递增序列 5 4 4 3 2 1 1若该序列成立则第一个人有5个邻居假设第一个人的五个邻居分别是2,3,4,5,6
当第一个人搬走了剩下的人邻居个数为 3 3 2 1 0 1排序后为为3 3 2 1 1 0
当第二个人搬走了剩下的人邻居个数为 2 1 0 1 0排序后为为2 1 1 0 0
当第三个人搬走了剩下的人邻居个数为 0 0 0 0此时该序列成立。 特别说明若要用贪心算法求解某问题的整体最优解必须首先证明贪心思想在该问题的应用结果就是最优解 sort函数的使用
头文件 #includealgorithm
函数用法
sort(首地址尾地址1cmp函数);
当不传入cmp函数时默认递增
例 struct node{int a;double b;}arr[100];// 要求先按a升序若a相等则按b降序bool cmp(node x, node y){if(x.a ! y.a){return x.a y.a;}return x.b y.b;}
