PTA团体程序设计天梯赛L2真题讲解L2-017-020

官网https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7

L2-017 人以群分

题目大意：根据活跃度将人群分为内向型（活跃度低）和外向型（活跃度高）两类，要求两类人数尽可能接近，且总活跃度的差值尽可能大。输出两类的人数与总活跃度差值的绝对值。

解题思路：

1. 将所有活跃度从小到大排序，前半部分划分为内向型，后半部分划分为外向型。该划分方式能保证在人数最接近的前提下，两组总活跃度的差值最大。
2. 人数分配规则：总人数为偶数时两组人数相等；总人数为奇数时，外向型人数比内向型多1人（多的一人归入高活跃度组可最大化差值）。
3. 分别计算两组的活跃度总和，差值为外向总和减去内向总和。

正解代码

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=1e5+9;intn,a[N],sum1,sum2;signedmain(){cin>>n;for(inti=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);for(inti=1;i<=n/2;i++)sum1+=a[i];for(inti=n;i>n/2;i--)sum2+=a[i];printf("Outgoing #: %lld\n",n-n/2);printf("Introverted #: %lld\n",n/2);printf("Diff = %lld\n",sum2-sum1);return0;}

代码解析：

• 对活跃度数组升序排序，前n/2个元素求和为内向组总活跃度，剩余元素求和为外向组总活跃度。
• 内向组人数为n/2，外向组人数为n - n/2，天然满足奇数人数时外向组多一人的规则。
• 使用long long存储总和，避免数据溢出。

L2-018 多项式A除以B

本题为高难度模拟题，赛场建议放弃，优先保证其他题目的得分。

L2-019 悄悄关注

题目大意：给定用户的关注列表和点赞记录，筛选出“不在关注列表中、且点赞次数大于所有点赞平均次数”的用户，按用户ID字母序升序输出；若无符合条件的用户，输出Bing Mei You。

解题思路：

1. 用集合存储所有关注用户ID，实现快速查询某个用户是否在关注列表中。
2. 读入全部点赞记录，累加总点赞次数，计算平均点赞数。
3. 遍历所有点赞用户，筛选出满足「不在关注列表」且「点赞次数 > 平均值」的用户。
4. 将筛选结果按ID字典序升序排序后输出，结果为空则输出指定提示字符串。

正解代码

#include<bits/stdc++.h>usingnamespacestd;intn,k;doublesum;string s;set<string>st;structno{string id;doublelk;booloperator<(no others)const{returnlk<others.lk;}}a[10010];intmain(){cin>>n;for(inti=0;i<n;i++){cin>>s;st.insert(s);}cin>>k;for(inti=0;i<k;i++){cin>>a[i].id>>a[i].lk;sum+=a[i].lk;}sum/=k;sort(a,a+k);boolfd=0;vector<string>v;for(inti=k-1;i>=0;i--){if(a[i].lk<sum)break;if(!st.count(a[i].id)){fd=1;v.push_back(a[i].id);}}sort(v.begin(),v.end());//按ID字母序输出for(inti=0;i<v.size();i++)cout<<v[i]<<'\n';if(!fd)cout<<"Bing Mei You";return0;}

代码解析：

• 用set<string>存储关注列表，查询时间复杂度为O(logN)，效率较高。
• 结构体存储每个点赞用户的ID和点赞次数，遍历筛选符合条件的用户存入vector。
• 对结果vector调用sort，利用string的默认字典序比较规则完成排序。
• 用标记变量记录是否存在符合条件的用户，控制最终输出内容。

L2-020 功夫传人

题目大意：祖师爷（编号0）初始功力为Z，武功每向下传承一代，功力减弱 r%；若弟子为“得道者”，其功力会放大指定倍数。计算所有得道者的功力总和，只保留整数部分。

解题思路：

• 师门谱系是典型的多叉树结构，使用DFS遍历整棵树即可。

1. 从根节点（祖师爷）出发，初始功力为Z。
2. 每递归到下一层（徒弟），功力乘以折扣系数(100 - r) / 100。
3. 若当前节点是得道者，直接计算其最终功力并累加到总和，不再向下递归（得道者无徒弟）。

正解代码

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=1e5+9;vector<int>v[N];intb[N];boolst[N];intn;doubleans,z,r;voiddfs(intid,doubleeg){if(st[id]){ans+=b[id]*eg;return;}for(inti=0;i<v[id].size();i++){dfs(v[id][i],eg*(100-r)/100);}}signedmain(){cin>>n>>z>>r;doubleeg;eg=z;for(inti=0;i<n;i++){intx;cin>>x;if(x!=0)for(intj=0;j<x;j++){inty;cin>>y;v[i].push_back(y);}else{inty;cin>>y;st[i]=1;b[i]=y;}}dfs(0,eg);cout<<(int)ans;return0;}

代码解析：

• 用vector<int>数组存储每个人的徒弟列表，构建树结构。
• 布尔数组标记是否为得道者，数组存储得道者的功力放大倍数。
• DFS函数接收当前节点编号与当前功力值：遇到得道者则累加答案并返回；否则遍历所有徒弟，递归传递衰减后的功力值。
• 最终结果强制转换为int，按题目要求截断取整。