【团体程序设计天梯赛 往年关键真题 详细分析&完整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
输出样例：
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;
}
