计算机算法设计与分析第四章贪心算法上机题

我就是我 2023-10-03 17:44 130阅读 0赞

#### 文章目录 ####

*  7-1 最优合并问题 (20 分)
 *   *  题目描述
     *  基本思路
     *  参考代码
     *   *  方法一（sort）
         *  方法二（priority\_queue）
 *  7-5 会场安排问题 (15 分)
 *   *  题目描述
     *  基本思路
     *  参考代码
 *  7-4 货币找零 (15 分)
 *   *  题目描述
     *  基本思路
     *  参考代码

## 7-1 最优合并问题 (20 分) ##

### 题目描述 ###

题目来源：王晓东《算法设计与分析》

给定k 个排好序的序列, 用 2 路合并算法将这k 个序列合并成一个序列。 假设所采用的 2 路合并算法合并 2 个长度分别为m和n的序列需要m+n-1 次比较。试设 计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。 为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。

输入格式:  
第一行有 1 个正整数k，表示有 k个待合并序列。 第二行有 k个正整数，表示 k个待合并序列的长度。

输出格式:  
输出最多比较次数和最少比较次数。

输入样例:  
在这里给出一组输入。例如：

4
    5 12 11 2

输出样例:  
在这里给出相应的输出。例如：

78 52

### 基本思路 ###

类似“哈夫曼树”的实现  
法一：sort  
法二：priority\_queue  
![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_20_color_FFFFFF_t_70_g_se_x_16]  
![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_20_color_FFFFFF_t_70_g_se_x_16 2]

### 参考代码 ###

#### 方法一（sort） ####

//sort
    #include <iostream>
    #include <algorithm>
    using namespace std;
    bool cmp(int a,int b)
    {
        
    	return a>b;
    }
    int main()
    {
        
    	int n;
    	cin>>n;
    	int a[n];
    	int b[n];
    	int num;
    	for(int i=0;i<n;i++) {
        
    		cin>>num;
    		a[i]=num;
    		b[i]=num;
    	}
    	int sum_min=0;
    	for(int i=0;i<n-1;i++){
        
    		sort(a+i,a+n);//注意每次循环都需排序（选出最大or最小的） 
    		a[i+1]+=a[i];
    		sum_min+=a[i+1]-1;
    		
    	}
    	
    	int sum_max=0;
    	for(int i=0;i<n-1;i++){
        
    		sort(b+i,b+n,cmp);
    		b[i+1]+=b[i];
    		sum_max+=b[i+1]-1;
    	}
    	cout<<sum_max<<" "<<sum_min<<endl;
    } 
    //priority queue

#### 方法二（priority\_queue） ####

//priority_queue
    #include <bits/stdc++.h>
    using namespace std;
    int main(){
        
    	int n;
    	cin>>n;
    	int a[n];
    	for(int i=0;i<n;i++)
    	{
        
    		cin>>a[i];
    	}
    	priority_queue<int> p1;//大顶堆 
    	for(int i=0;i<n;i++)
    	{
        
    		p1.push(a[i]);
    	}
    	int cnt_res1=0;
    	int cnt_each1=0;
    	int top;
    	while(p1.size()>=2)
    	{
        
    		top=p1.top();
    		p1.pop();
    		cnt_each1=top+p1.top();//第一+“第二” 
    		p1.pop();
    		p1.push(cnt_each1);
    		cnt_res1+=cnt_each1-1;
    	}
    	cout<<cnt_res1<<" ";//78
    	priority_queue<int,vector<int>,greater<int> >p2;//小顶堆
    	 for(int i=0;i<n;i++)
    	{
        
    		p2.push(a[i]);
    	}
    		int cnt_res2=0;
    	int cnt_each2=0;
    	int top2;
    	while(p2.size()>=2)
    	{
        
    		top2=p2.top();
    		p2.pop();
    		cnt_each2=top2+p2.top();//第一+“第二” 
    		p2.pop();
    		p2.push(cnt_each2);
    		cnt_res2+=cnt_each2-1;
    	}
    		cout<<cnt_res2;
    	
    }

> [C++ priority\_queue使用方法详细介绍][C_ priority_queue]

## 7-5 会场安排问题 (15 分) ##

### 题目描述 ###

题目来源：王晓东《算法设计与分析》

假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的 贪心算法进行安排。（这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个 顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小 会场数。）

输入格式:  
第一行有 1 个正整数k，表示有 k个待安排的活动。 接下来的 k行中，每行有 2个正整数，分别表示 k个待安排的活动开始时间和结束时间。时间 以 0 点开始的分钟计。

输出格式:  
输出最少会场数。

输入样例:

5
    1 23
    12 28
    25 35
    27 80
    36 50

输出样例:  
在这里给出相应的输出。例如：

### 基本思路 ###

![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_20_color_FFFFFF_t_70_g_se_x_16 3]

### 参考代码 ###

#include <bits/stdc++.h>
    using namespace std;
    typedef struct time{
        
    	int start;
    	int end;
    	int visited=0;
    }m_time;
    bool cmp(m_time a,m_time b)
    {
        
    	if(a.start==b.start)
    	{
        
    		return a.end<b.end;//start相同，按end从小到大排 
    	}
    	return a.start<b.start;
    }
    int main()
    {
        
    	int n;
    	cin>>n;
    	m_time a[n];
    	//vector<m_time> v;
    	for(int i=0;i<n;i++)
    	{
        
    		cin>>a[i].start>>a[i].end;
    		//v.push_back(a[i]);
    	} 
    	sort(a,a+n,cmp);
    	int cnt_res=0;
    	int left=n;
    	//每一个舞台安排尽量多的活动 
    		for(int i=0;i<n;i++)
    		{
        
    			int end_time;//每个“起始活动”的结束时间，用于判断后面是否可以与此活动同台演出 
    			if(a[i].visited==0)//=0表示此活动尚未安排 
    			{
        
    				cnt_res++;
    			end_time=a[i].end;
    			
    			for(int j=i+1;j<n;j++)
    			{
        
    				if(a[j].start>=end_time&&a[j].visited==0){
        
    					a[j].visited=1;
    					end_time=a[j].end;//更新结束时间，“向后比较” 
    					
    				}
    			}
    		}
    			}
    		cout<<cnt_res<<endl;
    	
    }

## 7-4 货币找零 (15 分) ##

### 题目描述 ###

人民币的面值有100、50、20、10、5、2、1元。请你输出找零纸币数最少的方案

输入格式:  
两个整数，分别表示付款金额和消费金额

输出格式:  
输入找零方案。包含若干行，每行包含两个数字，纸币面额和纸币数量

输入样例:

10 3

输出样例:  
在这里给出相应的输出。例如：

5 1
    2 1

### 基本思路 ###

想算出需要找多少钱  
从大面值开始遍历  
尽量选取最多张的大面值

### 参考代码 ###

#include <iostream>
    using namespace std;
    int main(){
        
    	int v[]={
        100,50,20,10,5,2,1};
    	int cnt[7]={
        0};
    	int pay,cost;
    	cin>>pay>>cost;
    	int m=pay-cost;
    	for(int i=0;i<7;i++)
    	{
        
    		int max=0;
    		if(m>=v[i])
    		{
        
    			max=m/v[i];
    			m-=v[i]*max;
    			cnt[i]+=max;
    		}
    	} 
    	for(int i=0;i<7;i++)
    	{
        
    		if(cnt[i]!=0)
    		{
        
    			cout<<v[i]<<" "<<cnt[i];
    			if(i!=6)
    			{
        
    				cout<<endl;
    			}
    		}
    	}
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/fee68c54f9994435aec180d75780f580.jpg?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAR0NUVFRUVFQ=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/350412fdce1247ba8dce663b033cd1dd.jpg?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAR0NUVFRUVFQ=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/07e85ec075ff46149326e22d04c45295.jpg?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAR0NUVFRUVFQ=,size_20,color_FFFFFF,t_70,g_se,x_16
[C_ priority_queue]: https://blog.csdn.net/weixin_45826022/article/details/103297284?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163714846916780357229340%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=163714846916780357229340&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-103297284.first_rank_v2_pc_rank_v29&utm_term=priority_queue%E7%94%A8%E6%B3%95&spm=1018.2226.3001.4187
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAR0NUVFRUVFQ_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/33df1795de1243f5ba5fe8715ebb2b36.jpg?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAR0NUVFRUVFQ=,size_20,color_FFFFFF,t_70,g_se,x_16