【团体程序设计天梯赛 往年关键真题 详细分析完整AC代码】L2-003 月饼(贪心) L2-004 这是二叉搜索树吗? (数据结构)

本文主要是介绍【团体程序设计天梯赛 往年关键真题 详细分析完整AC代码】L2-003 月饼(贪心) L2-004 这是二叉搜索树吗? (数据结构),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

L2-003 月饼 贪心

月饼是中国人在中秋佳节时吃的一种传统食品,不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量,请你计算可以获得的最大收益是多少。

注意:销售时允许取出一部分库存。样例给出的情形是这样的:假如我们有 3 种月饼,其库存量分别为 18、15、10 万吨,总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨,那么我们最大收益策略应该是卖出全部 15 万吨第 2 种月饼、以及 5 万吨第 3 种月饼,获得 72 + 45/2 = 94.5(亿元)。

输入格式:

每个输入包含一个测试用例。每个测试用例先给出一个不超过 1000 的正整数 N 表示月饼的种类数、以及不超过 500(以万吨为单位)的正整数 D 表示市场最大需求量。随后一行给出 N 个正数表示每种月饼的库存量(以万吨为单位);最后一行给出 N 个正数表示每种月饼的总售价(以亿元为单位)。数字间以空格分隔。

输出格式:

对每组测试用例,在一行中输出最大收益,以亿元为单位并精确到小数点后 2 位。

输入样例:

3 20
18 15 10
75 72 45

输出样例:

94.50

分析:

按照单价排序,优先选择单价最高的。库存量和总售价不一定为整数

代码:

#include<bits/stdc++.h>
using namespace std;const int N=1e5+5;
typedef long long ll;struct node{double num,price,dj;
}Mooncake[N];
bool cmp(node a,node b){ return a.dj>b.dj; }
int main(){int n,m,k=0,i;cin>>n>>m;for(i=0;i<n;i++) cin>>Mooncake[i].num;for(i=0;i<n;i++) cin>>Mooncake[i].price;for(i=0;i<n;i++) Mooncake[i].dj=Mooncake[i].price/Mooncake[i].num;sort(Mooncake,Mooncake+n,cmp);double ans=0;while(k<n){if(Mooncake[k].num<=m){m-=Mooncake[k].num;ans+=Mooncake[k].price;}else{ans+=Mooncake[k].dj*m;break;}k++;}printf("%.2lf\n",ans);return 0;
}

L2-004 这是二叉搜索树吗? 数据结构

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树:对于任一结点,

  • 其左子树中所有结点的键值小于该结点的键值;
  • 其右子树中所有结点的键值大于等于该结点的键值;
  • 其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”,即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列,现请你编写程序,判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式:

输入的第一行给出正整数 N(≤1000)。随后一行给出 N 个整数键值,其间以空格分隔。

输出格式:

如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果,则首先在一行中输出 YES ,然后在下一行输出该树后序遍历的结果。数字间有 1 个空格,一行的首尾不得有多余空格。若答案是否,则输出 NO

输入样例 1:

7
8 6 5 7 10 8 11

输出样例 1:

YES
5 7 6 8 11 10 8

输入样例 2:

7
8 10 11 8 6 7 5

输出样例 2:

YES
11 8 10 7 5 6 8

输入样例 3:

7
8 6 8 5 10 9 11

输出样例 3:

NO

分析:

因为前序遍历是根左右,所以在插入某个孩子节点时,它的父节点肯定已经被插入了,又由于搜索树的限制关系(小的左边,大的右边),所以可以确定一棵唯一的二叉搜索树,然后对其进行两种不同的前序遍历,再分别与题目所给的序列比较即可。

代码:

#include<bits/stdc++.h>
using namespace std;const int N=1e5+5;
typedef long long ll;struct node{node *l,*r;int data;
};
typedef node* Tree;
//s1为正常前序遍历,s2为左右儿子颠倒的前序遍历,s为输入序列
vector<int> s1,s2,s,ans;
int n,cnt,x;
Tree build(Tree root,int x){if (root == NULL) {//到达最底部,创建新节点,并赋值root = new(node);root->l = root->r = NULL;root->data = x;}//x小于当前节点,说明x在root的左半边,向左递归else if (x < root->data) root->l = build(root->l, x);else root->r = build(root->r, x);return root;
}
//正常前序遍历
void pre1(Tree root) {if (root == NULL) return;s1.push_back(root->data);pre1(root->l);pre1(root->r);
}
//左右颠倒的前序
void pre2(Tree root) {if (root == NULL) return;s2.push_back(root->data);pre2(root->r);pre2(root->l);
}
//正常后序
void post1(Tree root) {if (root == NULL) return;post1(root->l);post1(root->r);ans.push_back(root->data);
}
//左右颠倒的后序
void post2(Tree root) {if (root == NULL) return;post2(root->r);post2(root->l);ans.push_back(root->data);
}
//比较两个序列是否完全相同
bool judge(vector<int> a) {for (int i = 0; i < a.size(); i++) if (a[i] != s[i]) return 0;return 1;
}
int main(){cin >> n;for (int i = 0; i < n; i ++) cin >> x,s.push_back(x);Tree root=NULL;for (int i = 0; i < n; i ++)root = build(root, s[i]);pre1(root); pre2(root);if (judge(s1)) {//说明所给序列是二叉搜索树的前序遍历post1(root);puts("YES");for (int i = 0; i < n; i++)printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');}else if (judge(s2)) {//是镜像的前序遍历puts("YES");post2(root);for (int i = 0; i < n; i++)printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');}else //不是二叉搜索树puts("NO");return 0;
}

这篇关于【团体程序设计天梯赛 往年关键真题 详细分析完整AC代码】L2-003 月饼(贪心) L2-004 这是二叉搜索树吗? (数据结构)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/909387

相关文章

大模型研发全揭秘:客服工单数据标注的完整攻略

在人工智能(AI)领域,数据标注是模型训练过程中至关重要的一步。无论你是新手还是有经验的从业者,掌握数据标注的技术细节和常见问题的解决方案都能为你的AI项目增添不少价值。在电信运营商的客服系统中,工单数据是客户问题和解决方案的重要记录。通过对这些工单数据进行有效标注,不仅能够帮助提升客服自动化系统的智能化水平,还能优化客户服务流程,提高客户满意度。本文将详细介绍如何在电信运营商客服工单的背景下进行

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl