2022牛客寒假算法基础集训营1
比赛链接
https://ac.nowcoder.com/acm/contest/23106
A.九小时九个人九扇门
题目描述
在打越钢太郎的著名解谜游戏系列《极限脱出》的第一作《九小时九个人九扇门》中，有这样一个有趣的设定：游戏中，99位主人公被困在一座大型的豪华巨轮中，每个人手上都有一个奇怪的手表，手表上有一个数字，\(9\)个人的数字分别是\(1-9\)；在巨轮中，还有很多紧闭的数字门，每扇数字门上也有一个\(1-9\)的数字，要想打开数字门逃出生天，主角们必须要满足一个奇怪的条件：
\(k\)个人能够打开门上数字为\(d\)的一扇数字门，当且仅当这\(k\)个人的腕表数字之和的数字根恰好为\(d\)。
一个数字的数字根是指：将该数字各数位上的数字相加得到一个新的数，直到得到的数字小于\(10\)为止，例如，\(149\)的数字根为\(149 => 1+4+9=14 => 1+4=5\)，故\(149\)的数字根为\(5\)。我们约定，小于\(10\)的数字，其数字根就为其本身。
例如，如果游戏中的一宫（手表数字为\(1\)）、四叶（手表数字为\(4\)）、八代（手表数字为\(8\)）三人组合在一起，就可以打开编号为\(4\)的数字门，这是因为\(1+4+8=13\)，而\(13\)的数字根为\(4\)。
现在，你是游戏的主角，淳平，你知道船上包括自己在内的\(n\)个人的手表数字，为了分析局势，你想要计算出可以打开\(1-9\)号门的人物组合有多少种，你可以完成这项任务吗？
输入描述:
输入的第一行包含一个整数\(n(1\leq n \leq 10^{5})\)，主人公的数量。
下面一行\(n\)个数，第\(i\)个数字\(a_{i}(1\leq a_{i}\leq 10^{9})\)表示第\(i\)位主人公的腕表数字。
输出描述:
你需要输出\(9\)个数字，第\(i\)个数字表示有多少种不同的人物组合，可以打开编号为\(i\)的数字门。
答案可能很大，请你将答案对\(998244353\)取模后输出。
输入
9
1 2 3 4 5 6 7 8 9
输出
56 56 58 56 56 58 56 56 59
解题思路
01背包变形
数字根结论：一个数的数字根等于这个数对9取模的结果（特别地，取模得
0则数字根为9）
- 状态表示：\(f[i][j]\) 表示从前 \(i\) 个数中选若干数使其之和的数字根为 \(j\) 的方案数
- 状态计算：
-
- \(f[i][j]+=1\)
-
- \(f[i][j]+=f[i-1][(j-a[i]%9+9)%9]+f[i-1][j]\)
分析：先分为两种情况：选择一个数和选择大于一个数，选择一个数即 \(f[i][j]+=1\)，选择大于一个数也可考虑两种情况：是否选择最后一个数，几种情况相加即为总的方案数
- \(f[i][j]+=f[i-1][(j-a[i]%9+9)%9]+f[i-1][j]\)
代码
// Problem: 九小时九个人九扇门
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23106/A
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// %%%Skyqwq
#include
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long LL;
typedef pair PII;
template bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int mod=998244353;
int n,a[100005],f[100005][10];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
f[1][a[1]%9]=1;
for(int i=2;i<=n;i++)
{
f[i][a[i]%9]++;
for(int j=0;j<9;j++)
f[i][j]=(f[i][j]+f[i-1][(j-a[i]%9+9)%9]+f[i-1][j])%mod;
}
for(int i=1;i<=8;i++)
printf("%d ",f[n][i]);
printf("%d",f[n][0]);
return 0;
}
C.Baby's first attempt on CPU
题目描述
在硬件小学期课程上，学生们要分组使用Verilog编写流水线CPU，并学会处理各种流水线CPU中常见的相关问题，包括数据相关、结构相关与控制（转移）相关，炸鸡块君也学到了许多。现在，他也要教你解决流水线CPU中数据相关下的先写后读相关问题。
在汇编语言程序中，程序是由多句汇编语句组成的，每句汇编语句会从寄存器中读一些数据（可能不读）和向寄存器中写一些数据（可能不写）。但由于CPU流水线式的架构，一条语句A写入寄存器的数据若想被语句B读到，则语句B和A之间至少要间隔三条语句，否则B将读到该寄存器中的老数据而不是A刚刚写入的数据，这被称为寄存器的先写后读相关问题。
例如，第一条语句写入了十号寄存器一个数据，若想写一个读取十号寄存器中数据的语句，则该语句最快也要等到第五句才可以（因为此时两条语句才恰好间隔三句）。
解决先写后读相关问题往往可以使用插入空操作（空操作也是一种汇编语句，该语句什么都不做，只起到占位的作用）的方法，即填充一些什么都不做的语句到原程序中。例如，现在第一条语句写入了八号寄存器、第二条语句读取了八号寄存器，因此存在对八号寄存器的先写后读相关问题，可以通过在之中插入三句空语句来解决该问题，即原程序在插入后变为：原第一条语句、空语句、空语句、空语句、原第二条语句。
现在，给出一个原有\(n\)个语句的汇编程序，并给出程序中语句之间发生先写后读相关的情况，请你求出最少添加多少个空语句可以使得该程序完全不存在任何先写后读相关问题。
输入描述:
输入第一行包括一个整数\(n(3\leq n \leq 100)\)，程序原有语句总数。
接下来有\(n\)行，第\(i\)描述了第\(i\)条程序语句，每行有三个数字。第\(i\)行第\(j\)个数字\(a_{i,j}\in\{0,1\}\)表示第\(i\)句与第\(i-j\)句间是否发生了先写后读相关，为\(1\)表示有发生先写后读相关（即第\(i-j\)句写入了某一寄存器，而第\(i\)句又要读取同一寄存器），为\(0\)表示没有。
输入保证对于\(i-j\leq0\)的\(a_{i,j}\)有\(a_{i,j}=0\)成立。
（你可以通过样例进一步理解输入的含义）
输出描述:
输出一个整数，表示为完全消除先写后读相关至少需加入多少条空语句。
输入
4
0 0 0
1 0 0
0 1 0
0 0 0
输出
3
说明
输入表示发生先写后读相关问题的语句有：第二句读了第一句所写的寄存器、第三句读了第一句所写的寄存器。
一种插入三个空语句的最优策略为变成：
原第一句、空语句、空语句、空语句、原第二句、原第三句、原第四句。
解题思路
模拟
不妨打印出前 \(5\) 个句子之间的关系：
1:0 -1 -2
2:1 0 -1
3:2 1 0
4:3 2 1
5:4 3 2
对于第一个句子不用考虑，第二个句子只用考虑和第一个句子之间的关系，第三个句子只用考虑和第一个和第二个句子之间的关系，这三种情况特殊处理，对于当前句子来说，只存在三种关系，并且优先选择靠的近的句子中间加空格越优，对于靠得最近的句子，如果有冲突，则加上三个空格，此时与其他句子断然不会有冲突，如果没有冲突的话，考虑靠得次近的句子，如果有冲突的话，考虑在最近的句子中间加上若干个空格，这些空格数由上一个句子与最近的句子之间的空格数决定，对于靠得最远的句子也是如此
- 时间复杂度：\(O(n)\)
代码
// Problem: Baby's first attempt on CPU
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23106/C
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// %%%Skyqwq
#include
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long LL;
typedef pair PII;
template bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
int n,res;
int main()
{
int a,b,c;
scanf("%d",&n);
int lst=0,lst1=0;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(i==1)continue;
else if(i==2)
{
if(a)lst=3,res+=3;
}
else if(i==3)
{
if(a)lst1=lst,lst=3,res+=3;
else if(b)
{
if(lst)lst1=lst,lst=0;
else
lst1=lst,lst=2,res+=2;
}
}
else
{
if(a)lst1=lst,lst=3,res+=3;
else if(b)
{
int t=2-lst;
if(t<=0)lst1=lst,lst=0;
else
lst1=lst,lst=t,res+=t;
}
else if(c)
{
if(lst1||lst)lst1=lst,lst=0;
else
lst1=lst,lst=1,res++;
}
else
lst1=lst,lst=0;
}
}
printf("%d",res);
return 0;
}
F.中位数切分
题目描述
给定一个长为\(n\)的数组\(a\)和一个整数\(m\)，你需要将其切成连续的若干段，使得每一段的中位数都大于等于\(m\)，求最多可以划分成多少段。
我们定义，偶数个数的中位数为中间两个数中较小的那一个，奇数个数的中位数就是正中间的数。如\([2,3,1,5]\)的中位数为\(2\)，\([2,3,1,2]\)的中位数为\(2\)，\([3,5,9,7,11]\)的中位数为\(7\)。
输入描述:
输入第一行是一个整数\(T(1\leq T\leq 20)\)，测试组数。
每个测试第一行是两个整数\(n,m(1\leq n\leq 10^5, 1\leq m \leq 10^9)\)，含义如题目所示。
第二行输入\(n\)个数，数组\(a\)，满足\(1\leq a_i\leq 10^9\)。
由于本题输入量较大，建议使用scanf等高效输入方式。
输出描述:
每个测试用例，输出一个整数，表示最多可以划分成多少段，若无论如何划分都不能满足条件，输出\(-1\)。
输入
4
5 4
10 3 2 3 2
5 3
5 2 3 3 2
2 5
4 5
5 2
10 3 2 3 2
输出
-1
1
-1
5
解题思路
数学
记数列中 \(≥??\) 的数字有 \(??????_??\) 个，\(<??\) 的数字有 \(??????_??\) 个，，则答案为 \(??????_?? ? ??????_??\)，该值 \(≤??\) 时输出 \(-1\)
证明：
记 \(??(??, ??)\) 为原数组中 \(??[??] … ??[??]\) 一段中的元素对应的 \(??????_1 ? ??????_2\) 的值
\(??()\) 的性质：
? \(??(??, ??) > 0\) 表示该段单独拿出来满足中位数 \(≥ ??\)；
? \(??(??, ??) = ?? (??, ??????) + ??(?????? + 1, ??)\)
原问题 \(?? (1, ?? )≤ 0\)时输出 \(?1\) 是显然的；
欲证明：\(??( 1, ??) > 0\) 时，\(??(1, ??)\) 即为原问题答案；
若可以找到一个位置 \(??????\)，使 \(?? (1, ??????) > 0\)&&\(?? (?????? + 1, ??) > 0\)，则
沿 \(??????\) 将数组切开得到的两部分中位数依然满足条件，此时区间数
\(+=1\)；
所以我们要探究下什么时候数组可以切:
定理：当且仅当 \(??( ??, ??) > 1\) 时存在一种切法使
\(?? (??, ?????? > 0)\)&&\(??(?????? + 1, ??) > 0\)
证明：
? 若有一个位置 \(??????\) 使得 \(?? (??, ??????) = 1\)，则该位置是满足条件的切
割位置，因为此时 \(?? (??, ??????) = 1 > 0\)，\(?? (?????? + 1, ??) = ?? (??, ??) ?
?? (??, ??????) > 1 ? 1 = 0\)；
? 又因为 \(?? (??, ?? ? 1) = 0\)（表示空区间）且 \(?? (??, ??) > 1\) 且 \(?? (??, ?? →
??(??, ?? + 1)\) 时值只会变化 \(1\)，因此过程中一定存在某一时刻 \(??????\) 使
得\(?? (??, ??????) = 1\)。
由上，只要 \(?? (??, ??) > 1\) 就可以切，而我们又希望切得尽可能多，
因此最终状态一定是所有切割得到的段都有 \(?? (??, ??) = 1\)（否则还
可以再切），因此，\(\sum_{l_i,r_i}f(l_i,r_i)=\)最终切成的段数,又因为初始时有\(\sum_{l_i,r_i}f(l_i,r_i)=f(1,n)-cnt_1-cnt_2\) 所以最终切成的段数 \(=??????_1 ? ??????_2\)，证毕。
- 时间复杂度：\(O(n)\)
代码
// Problem: 中位数切分
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23106/F
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// %%%Skyqwq
#include
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long LL;
typedef pair PII;
template bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
int main()
{
int t;
for(scanf("%d",&t);t;t--)
{
int n,m,x;
scanf("%d%d",&n,&m);
int cnt1=0,cnt2=0;
while(n--)
{
scanf("%d",&x);
cnt1+=x>=m;
cnt2+=x H.牛牛看云
题目描述
就像罗夏墨迹测试一样，同一片形状的云在不同人的眼中会看起来像各种各样不同的东西。
例如，现在天上飘过了一片长条状的云彩，hina说这片云长得像是薯条，moca说这片云长得像宾堡豆沙面包（5枚装），kasumi说这片云在闪闪发光，kokoro说这片云怎么看上去不开心呢，牛牛说这片云长得就像是：
\(\Sigma_{i=1}^{n} \Sigma_{j=i}^{n} |a_i+a_j-1000|\)
现在给出整数序列\(a\)，请你帮牛牛求出这个式子的值。
输入描述:
第一行包括一个整数\(n(3\leq n \leq 10^6)\)n，整数序列的长度。
第二行输入\(n\)个以空格分隔的整数\(a_i(0\leq a_i \leq 1000)\)，表示序列\(a\)。
输出描述:
输出一个整数，表示该式子的值。
输入
4
500 501 500 499
输出
8
解题思路
二分
考虑去绝对值，由于式子结果与序列的顺序无关，可以将序列排序，对于固定的 \(i\)，找出满足 \(a_i+a_j-1000>0\) 的第一个 \(j\)，其后面的数都满足该条件，即去绝对值后符号不变，前面的数要变号。另外注意第一个 \(j\) 出现的位置
- 时间复杂度：\(O(nlogn)\)
代码
// Problem: 牛牛看云
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23106/H
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// %%%Skyqwq
#include
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long LL;
typedef pair PII;
template bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
int n,a[1000005],s[1000005];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
int res=0;
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
for(int i=1;i<=n;i++)
{
int pos=upper_bound(a+1,a+1+n,1000-a[i])-a;
if(pos==n+1)
{
res+=1000*(n-i+1)-(s[n]-s[i-1])-(n-i+1)*a[i];
continue;
}
if(i<=pos)
{
res+=1000*(pos-1-i+1)-(s[pos-1]-s[i-1])-(pos-1-i+1)*a[i];
res+=s[n]-s[pos-1]+(n-pos+1)*a[i]-1000*(n-pos+1);
}
else
res+=s[n]-s[i-1]+(n-i+1)*a[i]-1000*(n-i+1);
}
printf("%d",res);
return 0;
}
枚举
由于数据量比较小，可以统计每个数出现的次数，要求的即为从序列中任选两个数求 \(|a_i+a_j-1000|\) 之和，可以从值域的角度来考虑，即从 \(0\) 到 \(1000\) 枚举 \(a_i\) 和 \(a_j\)，找出其可以形成的组合数再乘以 \(|a_i+a_j-1000|\) 即为这两个数的贡献，这里需要注意两个数可以相等或为同一个数
- 时间复杂度：\(O(10^6)\)
代码
// Problem: 牛牛看云
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23106/H
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// %%%Skyqwq
#include
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long LL;
typedef pair PII;
template bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
int n,cnt[1005];
LL res;
int main()
{
for(scanf("%d",&n);n;n--)
{
int a;
scanf("%d",&a);
cnt[a]++;
}
for(int i=0;i<=1000;i++)
for(int j=i;j<=1000;j++)
if(i==j)res+=1ll*abs(2*i-1000)*(cnt[i]+cnt[i]*(cnt[i]-1ll)/2ll);
else
res+=1ll*cnt[i]*cnt[j]*abs(i+j-1000);
printf("%lld",res);
return 0;
}
I.B站与各唱各的
题目描述
最近炸鸡块君在逛B站时发现了有趣的视频（https://www.bilibili.com/video/BV1MR4y1H7NV ），这种视频被称作"各唱各的"挑战，基于此，炸鸡块君提出了一种有趣的"各唱各的"游戏，其具体规则如下：
有\(n4位UP主在翻唱一首共\)m$句的歌曲；
\(n\)个UP主先各自独立的在不能与其他UP主交流的情况下录制一份唱歌的音频。对于这首歌中的每一句，每个UP主可以选择唱或不唱；
在所有UP主都录制完成后，将这\(n\)份唱歌的音频合到一起。若在合成后的音频中，某一句歌词所有人都没唱或同时被所有人都唱了，则认为这句唱失败了，否则认为这句唱成功了。
现在，炸鸡块君想知道：假设这\(n\)位UP主都足够聪明，每位UP主都精通编程且有一台计算速度无限快的超级计算机，但UP主之间不能交流，他们的目标是让成功唱出的句子数尽可能多，求期望唱成功的句子数量对\(10^9+7\)取模的结果。
输入描述:
输入第一行是一个整数\(T(1\leq T \leq 10^4)\)，测试用例的组数。
每组测试用例包括两个整数\(n,m(1\leq n,m\leq 10^9)\)，含义如题面所述。
输出描述:
对于每组样例输出一个整数，表示答案对\(10^9+7\)取模的结果。
若你的答案是一个形如\(\frac{p}{q}\)的分数，则应输出\(p\times q^{-1}\)对\(10^9+7\)取模的结果，之中4q^{-1}\(表示\)q$在模\(10^9+7\)意义下的逆元。
输入
1
1 100
输出
0
解题思路
数学
由于无法交流，每个人在唱每句时唯一的策略就是随机以 \(??_??\) 的概率决定唱
或不唱这一句，于是失败的概率即为：\(\prod p_i+ \prod (1-p_i)\)，当 \(??_1 = ??_2 = ? = ??_n=p\) 时最小，即失败概率为 \(p^n+(1-p)^n\)，当 \(p=1/2\) 时最小，最终一个句子成功的概率为 \(\frac{2^n-2}{2^n}\)，所有句子的期望为：\(m\times \frac{2^n-2}{2^n}\)
代码
// Problem: B站与各唱各的
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23106/I
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// %%%Skyqwq
#include
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long LL;
typedef pair PII;
template bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int mod=1e9+7;
int ksm(int a,int b,int p)
{
int res=1%p;
for(;b;b>>=1)
{
if(b&1)res=1ll*res*a%p;
a=1ll*a*a%p;
}
return res;
}
int main()
{
int t,n,m;
for(scanf("%d",&t);t;t--)
{
scanf("%d%d",&n,&m);
printf("%d\n",(1ll*m*((ksm(2,n,mod)-2+mod))%mod)%mod*ksm(ksm(2,n,mod),mod-2,mod)%mod);
}
return 0;
}
J.小朋友做游戏
题目描述
牛牛是一个幼儿园老师，他经常带小朋友们一起做游戏。
现在，牛牛的班里有\(A\)个安静的小朋友和\(B\)个闹腾的小朋友，牛牛想要从中选出恰好\(n\)个人来做游戏。这个游戏需要小朋友们手拉手围成一个圆圈，但不妙的是，如果两个闹腾的小朋友在圆圈中紧挨着，他们就会打闹，导致游戏无法进行。
每个小朋友还有一个幸福度\(v\)，若这位小朋友被选中参加游戏，则会使得班级的幸福度增加\(v\)。
请你求出，在满足上述所有限制的情况下，恰当的安排围成圆圈的方法，能使得班级的幸福度最大为多少。
输入描述:
输入第一行是一个整数\(T(1\leq T\leq 10^3)\)，测试数据组数。
每组测试数据，第一行是三个整数\(A,B,n(2\leq A,B\leq 10^4, 3\leq n \leq A+B)\)，含义如题目所示。
第二行是\(A\)个数，第\(i\)个数\(va_i(1\leq va_i \leq 10^4)\)表示某位安静小朋友的幸福度。
第三行是\(B\)个数，第\(i\)个数\(vb_i(1\leq vb_i \leq 10^4)\)表示某位闹腾小朋友的幸福度。
此外，保证所有测试数据的\((A+B)\)之和不会超过\(2*10^5\) 。
输出描述:
每组测试用例，输出一行一个整数，表示最大幸福度。若无论如何安排都不能进行游戏，输出$-14。
输入
3
3 6 7
1 3 4
5 4 3 4 3 5
4 6 7
1 3 4 1
5 4 3 4 3 5
7 7 7
1 2 3 4 5 6 7
9 8 7 6 5 4 3
输出
-1
23
46
解题思路
模拟
由题意，安静的小朋友的个数一定不小于 \(\left \lceil n/2 \right \rceil\)，接着枚举安静的小朋友的个数即可，注意对应的闹腾的小朋友的个数还要满足不能超过总的闹腾的小朋友的个数。取幸福度由大到小取即可
- 时间复杂度：\(O(t\times (AlogA+BlogB))\)
代码
// Problem: 小朋友做游戏
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23106/J
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// %%%Skyqwq
#include
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long LL;
typedef pair PII;
template bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
int t,n,A,B,a[10005],b[10005];
int main()
{
for(scanf("%d",&t);t;t--)
{
scanf("%d%d%d",&A,&B,&n);
for(int i=1;i<=A;i++)scanf("%d",&a[i]);
for(int i=1;i<=B;i++)scanf("%d",&b[i]);
sort(a+1,a+1+A,greater());
sort(b+1,b+1+B,greater());
for(int i=1;i<=A;i++)a[i]+=a[i-1];
for(int i=1;i<=B;i++)b[i]+=b[i-1];
int C=(n+2-1)/2;
if(A