练习地址
点此前往练习
淘汰分数
某比赛已经进入了淘汰赛阶段,已知共有n名选手参与了此阶段比赛，他们的得分分别是a_1,a_2….a_n,小美作为比赛的裁判希望设定一个分数线m，使得所有分数大于m的选手晋级，其他人淘汰。
但是为了保护粉丝脆弱的心脏，小美希望晋级和淘汰的人数均在[x,y]之间。
显然这个m有可能是不存在的，也有可能存在多个m，如果不存在，请你输出-1，如果存在多个，请你输出符合条件的最低的分数线。
输入描述:
输入第一行仅包含三个正整数n,x,y，分别表示参赛的人数和晋级淘汰人数区间。(1<=n<=50000,1<=x,y<=n)输入第二行包含n个整数，中间用空格隔开，表示从1号选手到n号选手的成绩。(1<=|a_i|<=1000)
输出描述:
输出仅包含一个整数，如果不存在这样的m，则输出-1，否则输出符合条件的最小的值。
输入例子1:
6 2 3
1 2 3 4 5 6
输出例子1:
3
思路：
对输入的分数升序排序，求符合条件的最低分数线，如果过线的人多，使用人数限制最大值 y作为过线人数，判断剩下的人数 是否在[x,y]区间 ：
(1) 如果在 直接返回；
(2)如果不在:
①如果人数少于x 则直接找到分数最低的第x个人即可。
②如果人数大于y 则证明找不到一个分数线满足条件。
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,x,y;
cin>>n>>x>>y;
int score;
vector<int> s;
while(cin>>score)
s.push_back(score);
sort(s.begin(),s.end());
if ((n-x>=x)&&(n-y<=y))
{
y=min(y,n-x);
cout<<s.at(n-y-1)<<endl;
}
else
cout<<-1<<endl;
return 0;
}
正则序列
我们称一个长度为n的序列为正则序列，当且仅当该序列是一个由1~n组成的排列，即该序列由n个正整数组成，取值在[1,n]范围，且不存在重复的数，同时正则序列不要求排序
有一天小团得到了一个长度为n的任意序列，他需要在有限次操作内，将这个序列变成一个正则序列，每次操作他可以任选序列中的一个数字，并将该数字加一或者减一。
请问他最少用多少次操作可以把这个序列变成正则序列？
输入描述:
输入第一行仅包含一个正整数n，表示任意序列的长度。(1<=n<=20000)输入第二行包含n个整数，表示给出的序列，每个数的绝对值都小于10000。
输出描述:
输出仅包含一个整数，表示最少的操作数量。
输入例子1:
5
-1 2 3 10 100
输出例子1:
103
思路：
对n个数升序排序，求每个数字移动的步数最少即让每个数字找距离下标[1,n]最近的位置填充。
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int> num(n);
int sum=0;
for(int i=0;i<n;i++)
{
cin>>num[i];
}
sort(num.begin(),num.end(),less<int>());
for(int i=1;i<=n;i++)
{
sum+=abs(num[i-1]-i);
}
cout<<sum;
return 0;
}
公司食堂
小美和小团所在公司的食堂有N张餐桌，从左到右摆成一排，每张餐桌有2张餐椅供至多2人用餐，公司职员排队进入食堂用餐。小美发现职员用餐的一个规律并告诉小团：当男职员进入食堂时，他会优先选择已经坐有1人的餐桌用餐，只有当每张餐桌要么空着要么坐满2人时，他才会考虑空着的餐桌；
当女职员进入食堂时，她会优先选择未坐人的餐桌用餐，只有当每张餐桌都坐有至少1人时，她才会考虑已经坐有1人的餐桌；
无论男女，当有多张餐桌供职员选择时，他会选择最靠左的餐桌用餐。现在食堂内已有若干人在用餐，另外M个人正排队进入食堂，小团会根据小美告诉他的规律预测排队的每个人分别会坐哪张餐桌。
输入描述:
第一行输入一个整数T（1<=T<=10），表示数据组数。
每组数据占四行，第一行输入一个整数N（1<=N<=500000）；
第二行输入一个长度为N且仅包含数字0、1、2的字符串，第i个数字表示左起第i张餐桌已坐有的用餐人数；
第三行输入一个整数M（1<=M<=2N且保证排队的每个人进入食堂时都有可供选择的餐桌）；
第四行输入一个长度为M且仅包含字母M、F的字符串，若第i个字母为M，则排在第i的人为男性，否则其为女性。
输出描述:
每组数据输出占M行，第i行输出一个整数j（1<=j<=N），表示排在第i的人将选择左起第j张餐桌用餐。
输入例子1:
1
5
01102
6
MFMMFF
输出例子1:
2
1
1
3
4
4
思路：
构建两个优先队列mp0和mp1（优先队列保证编号最小的餐桌在队首），用于存储空餐桌编号以及有一人在用餐的餐桌编号。然后遍历排队队伍s2，在遍历的过程中，每次都选择出队的餐桌：
(1) 对于男职员，如果还有已经坐了一人的餐桌，就接让mp1出队；否则让mp0出队，由于当前男职员坐了这个空桌，因此这个桌变成了已经有一人在用餐的餐桌，需要将其加入mp1。
(2) 对于女职员，如果还有空桌，就让mp0出队，由于当前女职员坐了这个空桌，因此这个桌变成了已经有一人在用餐的餐桌，需要将其加入mp1；否则直接让mp1出队。
需要注意输出换行符不能用endl，否则会超时，用’\n’ 不超时。
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m;
string s1,s2;
cin>>n;
cin>>s1;
cin>>m;
cin>>s2;
priority_queue<int,vector<int>,greater<int> > mp0,mp1;
for(int i=0;i<n;i++)
{
if(s1[i]=='0')
mp0.push(i+1);
else if(s1[i]=='1')
mp1.push(i+1);
}
for(int j=0;j<m;j++)
{
if(s2[j]=='M')
{
if(!mp1.empty())
{
int tmp=mp1.top();
mp1.pop();
cout<<tmp<<'\n';
}
else
{
int tmp=mp0.top();
mp0.pop();
cout<<tmp<<'\n';
mp1.push(tmp);
}
}
else
{
if(!mp0.empty())
{
int tmp=mp0.top();
mp0.pop();
cout<<tmp<<'\n';
mp1.push(tmp);
}
else
{
int tmp=mp1.top();
mp1.pop();
cout<<tmp<<'\n';
}
}
}
}
return 0;
}
最优二叉树II
小团有一个由N个节点组成的二叉树，每个节点有一个权值。定义二叉树每条边的开销为其两端节点权值的乘积，二叉树的总开销即每条边的开销之和。小团按照二叉树的中序遍历依次记录下每个节点的权值，即他记录下了N个数，第i个数表示位于中序遍历第i个位置的节点的权值。之后由于某种原因，小团遗忘了二叉树的具体结构。在所有可能的二叉树中，总开销最小的二叉树被称为最优二叉树。现在，小团请小美求出最优二叉树的总开销。
输入描述:
第一行输入一个整数N（1<=N<=300），表示二叉树的节点数。第二行输入N个由空格隔开的整数，表示按中序遍历记录下的各个节点的权值，所有权值均为不超过1000的正整数。
输出描述:
输出一个整数，表示最优二叉树的总开销。
输入例子1:
5
7 6 5 1 3
输出例子1:
45
例子说明1:
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6cQEtKik-1630722046771)(…/Typora_pics/image-20210903160158159.png)]
最优二叉树如图所示，总开销为7 * 1+6 * 5+5 * 1+1 * 3=45。
思路：
参考评论区中牛客585309717号的思路：
使用树形动态规划解决。
中序遍历特点：选取其中一个节点，其左边的节点都是其左子树上的节点，其右边的节点都是其右子树上的节点。
动态规划三步走：明确下标意义，寻找递推公式，dp数组初始化。
首先是dp数组的下标意义。两个二维数组，**ldp[i][j]**表示以以node[j+1]为根节点、node[i]到node[j]作为左子树节点的最优二叉树的权值；**r****dp[i][j]**表示以以node[i-1]为根节点、node[i]到node[j]作为右子树节点的最优二叉树的权值。
其次是递推公式：
l
d
p
[
a
]
[
b
]
=
m
a
x
(
l
d
p
[
a
]
[
i
−
1
]
+
n
o
d
e
[
i
]
∗
n
o
d
e
[
b
+
1
]
+
r
d
p
[
i
+
1
]
[
b
]
)
ldp[a][b]=max(ldp[a][i-1]+node[i]*node[b+1]+rdp[i+1][b])
ldp[a][b]=max(ldp[a][i−1]+node[i]∗node[b+1]+rdp[i+1][b])
r
d
p
[
a
]
[
b
]
=
m
a
x
(
l
d
p
[
a
]
[
i
−
1
]
+
n
o
d
e
[
i
]
∗
n
o
d
e
[
a
−
1
]
+
r
d
p
[
i
+
1
]
[
b
]
)
rdp[a][b]=max(ldp[a][i-1]+node[i]*node[a-1]+rdp[i+1][b])
rdp[a][b]=max(ldp[a][i−1]+node[i]∗node[a−1]+rdp[i+1][b])
最后是初始化，不需要初始化。
代码：
#include<bits/stdc++.h>
using namespace std;
int ldp[302][302]{};
int rdp[302][302]{};
int node[302]{};
void f(int a, int b)
{
int x, y;
ldp[a][b] = rdp[a][b] = 100000000;
for (int i = a; i <= b; ++i)
{
x = ldp[a][i - 1] + node[i] * node[b + 1] + rdp[i + 1][b];
y = ldp[a][i - 1] + node[i] * node[a - 1] + rdp[i + 1][b];
if (x < ldp[a][b])ldp[a][b] = x;
if (y < rdp[a][b])rdp[a][b] = y;
}
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> node[i];
}
for (int i = 0; i < n; ++i)
{
for (int j = 1; j <= n-i; j++)
{
f(j, j + i);
}
}
cout << ldp[1][n];
return 0;
}
