当前位置:   article > 正文

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

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

【团体程序设计天梯赛 往年关键真题 详细分析&完整AC代码】搞懂了赛场上拿下就稳

【团体程序设计天梯赛 往年关键真题 25分题合集 详细分析&完整AC代码】(L2-001 - L2-024)搞懂了赛场上拿下就稳了

【团体程序设计天梯赛 往年关键真题 25分题合集 详细分析&完整AC代码】(L2-025 - L2-048)搞懂了赛场上拿下这些分就稳了

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
  • 1
  • 2
  • 3

输出样例:

94.50
  • 1

分析:

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

代码:

#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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

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

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

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

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

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

输入格式:

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

输出格式:

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

输入样例 1:

7
8 6 5 7 10 8 11
  • 1
  • 2

输出样例 1:

YES
5 7 6 8 11 10 8
  • 1
  • 2

输入样例 2:

7
8 10 11 8 6 7 5
  • 1
  • 2

输出样例 2:

YES
11 8 10 7 5 6 8
  • 1
  • 2

输入样例 3:

7
8 6 8 5 10 9 11
  • 1
  • 2

输出样例 3:

NO
  • 1

分析:

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

代码:

#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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/471459
推荐阅读
相关标签
  

闽ICP备14008679号