算法2--贪心算法

1.老鼠和猫的交易

小老鼠准备了M磅的猫粮,准备去和看守仓库的猫做交易,因为仓库里有小老鼠喜欢吃的五香豆。

仓库有N个房间;
第i个房间有 J[i] 磅的五香豆,并且需要用 F[i] 磅的猫粮去交换;
老鼠不必交换该房间所有的五香豆,换句话说,它可以用 F[i] * a% 磅的猫粮去换取 J[i] * a% 磅的五香豆,其中a是一个实数。

现在,请帮忙计算一下,小老鼠最多能够得到多少磅的五香豆?

输入描述

输入包含多组测试用例。
每组测试数据首先一行是2个非负整数 M 和 N ,接着的 N 行,每行分别包含2个非负整数 J[i] 和 F[i] 。
输入数据以两个-1结束。
题目保证所有的数据不超过1000。

输出描述

请计算并输出小老鼠最多能够得到的五香豆数量。
每组数据输出一行,保留3位小数。

用例输入 1 

5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1

用例输出 1 

13.333
31.500

 学习:http://t.csdnimg.cn/gcmty

#include<bits/stdc++.h>
using namespace std;
int i;
int m,n;//猫粮数,房间数 
double tot=0;//换后的奶酪数 
struct room{double food;double cheese;
}a[100000];//数组开大一点 //sort函数的函数部分,从大到小排序 
bool cmp(room x,room y)
{return (x.cheese)/x.food>(y.cheese)/y.food;
}int main()
{while(scanf("%d %d",&m,&n)!=EOF){if(m==-1&&n==-1)	break;//结束条件 for(i=1;i<=n;i++)cin>>a[i].cheese>>a[i].food;//读入奶酪和猫粮 sort(a+1,a+1+n,cmp);//注意首地址 for(i=1;i<=n;i++){if(m-a[i].food>=0)//猫粮多于一只猫需要的猫粮 {tot=tot+1.0*a[i].cheese;//老鼠得到奶酪增加 m=m-a[i].food;//老鼠手中猫粮减少 }else//按比例购买最后一份猫粮 {tot=tot+1.0*a[i].cheese/a[i].food*m;break;} }printf("%.3lf\n",tot);tot=0;//注意结束后清零 }return 0;
}

2.田忌赛马

“田忌赛马”是中国历史上一个著名的故事。

大约2300年前,齐国大将田忌喜欢和国王赛马,并且约定:每赢一场,对方就要付200元。

假设已知田忌和国王的各自马匹的速度都不相同,请计算田忌最好的结果是什么。

输入描述

输入包含多组测试样例。
每组样例的第一行是一个整数n(n <= 1000),表示田忌和国王各自参赛的马匹数量。
接下来一行的n个整数表示田忌的马的速度,再接下来一行的n个整数表示国王的马的速度。
n为0时,表示输入数据的结束。

输出描述

每组数据输出一行,表示田忌最多能够赢得的金额。

用例输入 1 

3
92 83 71
95 87 74
2
20 19
22 18
0

用例输出 1 

200
0

一篇非常详细的文章:http://t.csdnimg.cn/qQPsV

题目分析:田忌赛马是一种权衡取舍,找适合策略,来收获最大利益的问题。在本题中我们先将田忌与齐王的马进行排序(在此,我以降序排序),然后选择最优解(比较快马):

1、田忌>齐王:正常比赛。

2、田忌<齐王:田忌慢马与齐王快马比赛。以慢换快

3、田忌=齐王(这一点十分容易忽略):这时我们可以观察慢马,若此时田忌>齐王,可以直接让慢马比赛(无疑时必赢的)。若此时田忌<=齐王,将田忌慢马与齐王快马比赛(与慢马或快马进行比赛,都是不可能赢的,何不换取更大的利益)。

#include<bits/stdc++.h>
using namespace std;//sort函数的函数部分,从大到小排序 
bool cmp(int x,int y)
{return x>y;
}int main()
{int n,a[10000],b[10000];while(scanf("%d",&n)!=EOF){if(n==0)	break; int i,j;for(i=0;i<n;i++)	cin>>a[i];for(i=0;i<n;i++)	cin>>b[i];//从快到慢排序 sort(a,a+n,cmp);sort(b,b+n,cmp);int l1=0,l2=0,sum=0;//排序后的左侧快马 int r1=n-1,r2=n-1;//排序后的右侧慢马 for(i=0;i<n;i++){if(a[l1]>b[l2])//快马:田忌 >齐王 ,正常比赛就可以赢 {l1++;l2++;sum++;}else if(a[l1]<b[l2])//快马:田忌<齐王 ,田忌慢马和齐王快马比赛,包输的 {r1--;l2++;sum--;}else if(a[r1]>b[r2])//快马相等,慢马田忌>齐王 ,正常比赛就赢了 {r1--;r2--;sum++;}else if(a[r1]<b[l2])//快马相等,慢马田忌<=齐王 ,田忌慢和齐王快比赛,包输的 {r1--;l2++;sum--;}}cout<<sum*200<<endl;}return 0;
}

3.搬桌子

丁爸信奥培训中心最近在富丽科技大厦租了一层楼,这层楼的形状如下:
 

10501.gif


由图可见,这层楼中间是走廊,两侧各有200个房间,编号如上图。

最近,丁爸信奥培训中心做了内部机构的调整,需要把一些桌子从一个房间搬到另外的房间。因为走廊很窄,但是桌子很大,所以同一段走廊每次只能通过一个桌子。

假设不论远近,每趟搬桌子都需要10分钟。同时,当你从房间i搬桌子到房间j的过程中,房间i到房间j之间的走廊都被占用,也就是说,在每个10分钟内,不能有多个任务共享同一段走廊。

现在,丁爸想知道:要完成所有的搬运任务,最少需要多少时间?

输入描述

输入包含T组测试用例。
每组测试用例首先是一个正整数N(1<=N<=200),表示需要搬运的桌子数量。
接下来N行,每行包含2个正整数s和t,表示需要将一个桌子从房间s搬到房间t。

输出描述

计算并输出完成所有的搬运任务需要的最少的时间,每组数据占一行。

用例输入 1 

3 
4 
10 20 
30 40 
50 60 
70 80 
2 
1 3 
2 200 
3 
10 100 
20 80 
30 50 

用例输出 1 

10
20
30

1. 我们可以把走廊模拟成一条线段,搬运桌子的起始位置模拟成这条线段上的区间;

2. 要想用时尽可能的少,我们应当让在同一时间段搬运的桌子尽可能多,也就是同一时间段线段上互不相交的区间尽可能多;

3. 对于那些存在重叠的区间,我们别无他法,只能分在不同时间段搬运;

4. 因此,我们需要找到区间之间的最大重叠次数,就是我们至少需要的时间;

注意点:由于房间分为两排,1和2, 3和4对应着同一段走廊,所以我们需要通过映射,把房间号对应成相应的走廊号。

#include<bits/stdc++.h>
using namespace std;
int main()
{int i,j,n,t,p[201];int s,d,temp,k,max;cin>>t;while(t--){for(i=0;i<=200;i++)	p[i]=0;//初识化 cin>>n;for(i=0;i<n;i++){cin>>s>>d;//使房间1和2对应的是一个位置 s=(s-1)/2;d=(d-1)/2;//从号码大的房间往回搬的情况if(s>d) {temp=s;s=d;d=temp;}for(k=s;k<=d;k++)	p[k]++;}max=-1;for(i=0;i<=200;i++){if(p[i]>max)	max=p[i];//通过某个地方最大次数为最小时间 }cout<<max*10<<endl;} return 0;	
}

4.今年暑假不AC

作为球迷,一定想看尽量多的完整的比赛,当然,作为新时代的好青年,你一定还会看一些其它的节目,比如新闻联播(永远不要忘记关心国家大事)、非常6+7、超级女生,以及王小丫的《开心辞典》等等,假设你已经知道了所有你喜欢看的电视节目的转播时间表,你会合理安排吗?(目标是能看尽量多的完整节目)

输入描述

输入数据包含多个测试实例,每个测试实例的第一行只有一个整数n(n<=100),表示你喜欢看的节目的总数,然后是n行数据,每行包括两个数据Tis​,Tie​ (1<=i<=n),分别表示第i个节目的开始和结束时间,为了简化问题,每个时间都用一个正整数表示。n=0表示输入结束,不做处理。

输出描述

对于每个测试实例,输出能完整看到的电视节目的个数,每个测试实例的输出占一行。

用例输入 1 

12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0

用例输出 1 

5

 若干个电视节目,自样例:按结束时选择合适然要按时间顺序来看。为了看更多的节目,需要尽
快看完一个节目再看另外一个节目,多看短节目才能看更多的节目。
        此题贪心的原则是,选择结束时间早的节目,留出时间看更多的节目。因此需要根据节目结束时间排序。

一开始,lastend=count=0,,循环i=0不对,然后改了一下,过了

#include<bits/stdc++.h>
using namespace std;
typedef struct node
{int start;int end;
}schedule;bool cmp(schedule x,schedule y)
{return x.end<y.end;
}int main()
{int i,n;schedule s[100000];while(scanf("%d",&n)!=EOF){if(n==0)	break;for(i=0;i<n;i++)cin>>s[i].start>>s[i].end;sort(s,s+n,cmp);int lastend=s[0].end;int count=1;for(i=1;i<n;i++){if(s[i].start>=lastend){count++;lastend=s[i].end;}}cout<<count<<endl;}return 0;	
}

5.奋勇争先续

还记得上次那个奋勇争先的题目吗,聪明的你帮助老师找出了第一名的同学。

现在,有个类似的问题:
已知每一位同学的解题数量和罚时,这次希望你能输出排名靠前的若干同学的名单。

注:排名首先依据做题数量,若做题数量相同,则比较罚时,罚时少的排名靠前。

输入描述

第一行是数据组数C,代表有C组测试实例。

每一组数据第一行两个整数N和M,N代表有N个人的成绩,M表示老师需要你输出前M名的名单。

接下来N行,每一行依次给出名字Name,做出的题目数量num和罚时time
( 1<=C<=10, 2<M<=N<=1000, Name的长度最大为10,1<=num<=10, 10<=time<=100000 )

输出描述

每组测试数据输出M行,第i行为第i名的名字、解题数量和罚时,中间用空格隔开。

每组数据后空一行。

用例输入 1 

1
3 3
Bob 5 50
Alice 4 46
John 5 48

用例输出 1 

John 5 48
Bob 5 50
Alice 4 46
#include<bits/stdc++.h>
using namespace std;
struct stu
{char name[100];int num;int time;
}s[1001];bool com(stu a,stu b)
{if(a.num<b.num)	return a.num>b.num;//从大到小else if(a.num==b.num) 	return a.time<b.time;//从小到大 
}int main()
{int t;cin>>t;while(t--){int n,m,i;cin>>n>>m;for(i=0;i<n;i++)scanf("%s%d %d",s[i].name,&s[i].num,&s[i].time);sort(s,s+n,com);for(i=0;i<m;i++)printf("%s %d %d\n",s[i].name,s[i].num,s[i].time);printf("\n"); }return 0;
} 

6.Degree Sequence of Graph G

Wang Haiyang is a strong and optimistic Chinese youngster. Although born and brought up in the northern inland city Harbin, he has deep love and yearns for the boundless oceans. After graduation, he came to a coastal city and got a job in a marine transportation company. There, he held a position as a navigator in a freighter and began his new life.

The cargo vessel, Wang Haiyang worked on, sails among 6 ports between which exist 9 routes. At the first sight of his navigation chart, the 6 ports and 9 routes on it reminded him of Graph Theory that he studied in class at university. In the way that Leonhard Euler solved The Seven Bridges of Knoigsberg, Wang Haiyang regarded the navigation chart as a graph of Graph Theory. He considered the 6 ports as 6 nodes and 9 routes as 9 edges of the graph. The graph is illustrated as below.

24541.jpg

According to Graph Theory, the number of edges related to a node is defined as Degree number of this node.

Wang Haiyang looked at the graph and thought, If arranged, the Degree numbers of all nodes of graph G can form such a sequence: 4, 4, 3,3,2,2, which is called the degree sequence of the graph. Of course, the degree sequence of any simple graph (according to Graph Theory, a graph without any parallel edge or ring is a simple graph) is a non-negative integer sequence?

Wang Haiyang is a thoughtful person and tends to think deeply over any scientific problem that grabs his interest. So as usual, he also gave this problem further thought, As we know, any a simple graph always corresponds with a non-negative integer sequence. But whether a non-negative integer sequence always corresponds with the degree sequence of a simple graph? That is, if given a non-negative integer sequence, are we sure that we can draw a simple graph according to it.?

Let’s put forward such a definition: provided that a non-negative integer sequence is the degree sequence of a graph without any parallel edge or ring, that is, a simple graph, the sequence is draw-possible, otherwise, non-draw-possible. Now the problem faced with Wang Haiyang is how to test whether a non-negative integer sequence is draw-possible or not. Since Wang Haiyang hasn’t studied Algorithm Design course, it is difficult for him to solve such a problem. Can you help him?

输入描述

The first line of input contains an integer T, indicates the number of test cases. In each case, there are n+1 numbers; first is an integer n (n<1000), which indicates there are n integers in the sequence; then follow n integers, which indicate the numbers of the degree sequence.

输出描述

For each case, the answer should be "yes"or “no” indicating this case is “draw-possible” or “non-draw-possible”.

用例输入 1 

2
6 4 4 3 3 2 2
4 2 1 1 1

用例输出 1 

yes
no

可图性的问题

sort()函数中的greater<int>()参数表示将容器内的元素降序排列。不填此参数,默认表示升序排列。

vector<int> a = {1,2,3};
sort(a.begin(), a.end(), greater<int>()); //将a降序排列
sort(a.begin(), a.end()); //将a升序排列

学习:http://t.csdnimg.cn/ENfbk

#include<bits/stdc++.h>
using namespace std;
int a[1006];int havel(int n);int main()
{int t;cin>>t;while(t--){int i,n,flag=0;cin>>n;for(i=0;i<n;i++)	cin>>a[i];if(havel(n)==1)		cout<<"yes"<<endl;else 				cout<<"no"<<endl;}return 0;
} int havel(int n)
{int i,j;for(i=0;i<n;i++){sort(a,a+n,greater<int>());//降序排序 if(a[0]==0)	return 1;//数组全0退出 for(j=1;j<=a[0];j++){if(a[j]==0)	return 0;//若为0,-1为负数无法构成简单图 else 	a[j]--;}a[0]=0;//当前点的度清零,会排在最后,不影响有度的点 }	
}

贪心算法:

在对问题求解时,总是作出在当前看来是最好的选择,也就是说,不从整体上加以考虑,所作出的仅仅是在某种意义上的局部最优解。

前提:排序

最长的事件序列问题

可图性判定

1.度序列:若把图G所有顶点的度数排成一个序列S,则称S为图G的度序列。

2.序列是可图的:一个非负整数组成的有限序列如果是某个无向图的度序列,则称该序列是可图的。

Havel-Hakimi定理:,每趟都要排序。

sort函数

sort(首地址,尾地址+1,[cmp函数])

1.这个函数可以传两个或三个参数

2.第一个参数是要排序的区间首地址

3.第二个参数是区间尾地址的下一地址

4.第三个参数不写,则缺省为递增排序

若为从大到小排序

int类型

int num[100];
bool cmp(int a,int b)
{return a>b;
}
sort(num,num+100,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;
}
sort(arr,arr+100,cmp);

浮点数比较大小不要直接==

double score;
if(fabs(x.score-y.score)>0.00001return x.score>y.score;

sort函数可以对数组的某一段进行排序。

若数组中元素是从下标1的位置开始存储,导致忘记修改sort的第一个参数。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/378494.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

大数据技术基础

一、大数据平台 1.大数据平台方案步骤&#xff1a; ①市场上有哪些大数据平台 ②硬件、系统、业务增长等方面 ③方案是否通过 通过后&#xff1a;按照一期目标投入 先虚拟环境部署联系&#xff0c;再实际部署 《大数据架构介绍》《Hadoop架构解析》《Hadoop集群规划》 《H…

微信小程序毕业设计-汽车维修项目管理系统项目开发实战(附源码+论文)

大家好&#xff01;我是程序猿老A&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;微信小程序毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计…

ollama + fastgpt 搭建免费本地知识库

目录 1、ollama ollama的一些操作命令: 使用的方式: 2、fastgpt 快速部署: 修改配置: config.json: docker-compose.yml: 运行fastgpt: 访问OneApi: 添加令牌和渠道: 登陆fastgpt,创建知识库和应用 3、总结: 附录: 1. 11434是ollama的端口: 2. m3e 测…

Java 中的正则表达式

转义字符由反斜杠\x组成&#xff0c;用于实现特殊功能当想取消这些特殊功能时可以在前面加上反斜杠\ 例如在Java中当\出现时是转义字符的一部分&#xff0c;具有特殊意义&#xff0c;前面加一个反斜可以取消其特殊意义&#xff0c;表示1个普通的反斜杠\&#xff0c;\\\\表示2个…

【排序算法】1.冒泡排序-C语言实现

冒泡排序&#xff08;Bubble Sort&#xff09;是最简单和最通用的排序方法&#xff0c;其基本思想是&#xff1a;在待排序的一组数中&#xff0c;将相邻的两个数进行比较&#xff0c;若前面的数比后面的数大就交换两数&#xff0c;否则不交换&#xff1b;如此下去&#xff0c;直…

Java红娘婚恋相亲交友系统小程序源码

红娘婚恋相亲交友小程序&#xff1a;遇见爱情&#xff0c;从指尖开始&#x1f496; &#x1f4f1; 掌中红娘&#xff0c;随时待命 &#x1f48c; 在这个数字化时代&#xff0c;爱情也迎来了它的新舞台——“红娘婚恋相亲交友小程序”。只需轻轻一点&#xff0c;你的专属红娘就…

git自动pull同步远程若干分支与本地若干分支

git自动pull同步远程若干分支与本地若干分支 假设远程代码仓库有100个分支&#xff0c;而本地只有10个本地分支与远程分支一一对应&#xff0c;现在要保持本地的这个10个分支与远程一致&#xff0c;最笨的方法是checkout到每个分支&#xff0c;然后一个一个的 git pull origin…

【文心智能体】前几天百度热搜有一条非常有趣的话题《00后疯感工牌》,看看如何通过低代码工作流方式实现图片显示

00后疯感工牌体验&#xff1a;https://mbd.baidu.com/ma/s/6yA90qtM 目录 前言比赛推荐工作流创建工作流入口创建工作流界面工作流界面HTTP工具卡点地方 总结推荐文章 前言 前几天百度热搜有一条非常有有趣《00后疯感工牌》。 想着通过文心智能体去一键生成00后疯感工牌是不是…

打包一个自己的Vivado IP核

写在前面 模块复用是逻辑设计人员必须掌握的一个基本功&#xff0c;通过将成熟模块打包成IP核&#xff0c;可实现重复利用&#xff0c;避免重复造轮子&#xff0c;大幅提高我们的开发效率。 接下来将之前设计的串口接收模块和串口发送模块打包成IP核&#xff0c;再分别调用…

华为USG6000V防火墙安全策略用户认证

目录 一、实验拓扑图 二、要求 三、IP地址规划 四、实验配置 1&#x1f923;防火墙FW1web服务配置 2.网络配置 要求1&#xff1a;DMZ区内的服务器&#xff0c;办公区仅能在办公时间内(9:00-18:00)可以访问&#xff0c;生产区的设备全天可以访问 要求2&#xff1a;生产区不…

list模拟实现【C++】

文章目录 全部的实现代码放在了文章末尾准备工作包含头文件定义命名空间类的成员变量为什么节点类是用struct而不是class呢&#xff1f;为什么要写get_head_node? 迭代器迭代器在list类里的实例化和重命名普通迭代器operator->()的作用是什么&#xff1f; const迭代器反向迭…

tkinter-TinUI-xml实战(12)pip可视化管理器

引言 pip命令行工具在平常使用方面确实足够简单&#xff0c;本项目只是作为TinUI多界面开发的示例。 当然&#xff0c;总有人想用GUI版pip&#xff0c;实际上也有。不过现在&#xff0c;我们就来手搓一个基于python和TinUI&#xff08;tkinter&#xff09;的pip可视化管理器。…

Java SpringAOP简介

简介 官方介绍&#xff1a; SpringAOP的全称是&#xff08;Aspect Oriented Programming&#xff09;中文翻译过来是面向切面编程&#xff0c;AOP是OOP的延续&#xff0c;是软件开发中的一个热点&#xff0c;也是Spring框架中的一个重要内容&#xff0c;是函数式编程的一种衍生…

模块化和包管理工具

一&#xff0c;模块化 1.定义 将一个复杂的程序文件依据一定规则&#xff08;规范&#xff09;拆分成多个文件的过程称之为 模块化 其中拆分出的 每个文件就是一个模块 &#xff0c;模块的内部数据是私有的&#xff0c;不过模块可以暴露内部数据以便其他模块使用 2.模块化…

【React Hooks原理 - forwardRef、useImperativeHandle】

概述 上文我们聊了useRef的使用和实现&#xff0c;主要两个用途&#xff1a;1、用于持久化保存 2、用于绑定dom。 但是有时候我们需要在父组件中访问子组件的dom或者属性/方法&#xff0c;而React中默认是不允许父组件直接访问子组件的dom的&#xff0c;这时候就可以通过forwa…

如何通过网络快速搜寻到自己的STM32设备

目录 一、问题概述 二、解决思路 三、代码实现 1.创建任务 2.UDP广播接收 一、问题概述 以前一直用RS232串口修改设备配置信息&#xff0c;但是现场施工人员的232线太细&#xff0c;经常容易断掉&#xff0c;这次准备用网口去修改&#xff0c;遇到了一个问题&#xff0c;…

【简历】惠州某二本学院:前端简历指导,秋招面试通过率为0

注&#xff1a;为保证用户信息安全&#xff0c;姓名和学校等信息已经进行同层次变更&#xff0c;内容部分细节也进行了部分隐藏 简历说明 这是一份25届二本同学&#xff0c;投递前端职位的简历&#xff0c;那么在校招环节二本同学主要针对的还是小公司&#xff0c;这个学校因为…

【B树、B-树、B+、B*树】

目录 一、B-树&#xff08;即B树&#xff09;的定义及操作1.1、定义1.2、操作1.2.1、查找1.2.2、插入1.2.3、删除 二、B树的定义及操作2.1、定义2.2、操作2.2.1、查找2.2.2、插入2.2.3、删除 三、B*树 一、B-树&#xff08;即B树&#xff09;的定义及操作 1.1、定义 B-tree即…

18_Shell好用工具:sort

18_Shell好用工具&#xff1a;sort 选项说明-k指定要排序的列-nnumber&#xff0c;按照数值大小排序-rreverse&#xff0c;逆序-t分隔符-u去重-o保存排序到文件 一、数字升序 #sort1.txt文件纯数字 #升序 sort -n sort1.txt #降序 sort -nr sort1.txt二、数字升序去重 #数字…

框架设计MVC

重点&#xff1a; 1.用户通过界面操作&#xff0c;传输到control&#xff0c;control可以直接去处理View&#xff0c;或者通过模型处理业务逻辑&#xff0c;然后将数据传输给view。 2.control包含了model和view成员。 链接&#xff1a; MVC框架详解_mvc架构-CSDN博客 MVC架…