P11523 [THUPC 2025 初赛] 摊位分配
题目描述
T 大学拥有数不胜数的优秀社团，例如核心成员达到 118 人的酸协（Students’ Association of Acid），刚成立就饱受关注的篹协（Students’ Association of Bamboo Basket），当然还有名扬四海的蒜协（Students’ Association of Garlic）。每学期伊始，T 大学都会统一举办全校性的社团招新活动。招新活动因规模庞大，故又被称为“百团大战”。如何把有限的场地像希尔伯特旅馆一般分配给各个社团，总是百团大战的负责人最头疼的问题。今年的负责人看中了蒜协将一整头大蒜干净利落地拆解成瓣的能力，因此找到了蒜协，希望可以用蒜法来解决分配摊位的问题。
具体而言，今年一共有
T
T
T 个社团希望参加百团大战，而可供百团使用的场地可以看成沿着学堂路排成一条直线的
H
H
H 个格子。为了鼓励社团之间的良性竞争，负责人决定根据每个社团上个学年对学校的贡献进行分配。按照提交参加申请的顺序，第
i
i
i 个社团上个学年对 T 大学的贡献为
u
i
u_i
ui。负责人希望根据以下规则将所有的
H
H
H 个格子分配给每个社团：
-
对于每个社团，计算序列
u
i
,
u
i
/
2
,
u
i
/
4
,
⋯
,
u
i
/
2
H
−
1
u_i, u_i/2, u_i/4, \\cdots,u_i/2^{H-1}
ui,ui/2,ui/4,⋯,ui/2H−1；
-
对于计算得到的
T
×
H
T\\times H
T×H 个数值，每次从中删去一个最大的，并将一个格子分配给相应社团的摊位，直到所有
H
H
H 个格子都分配完毕；如果出现多个最大值，
-
若有社团尚未分到格子，则优先分配给这样的社团，否则优先分配给原始的
u
i
u_i
ui 最大的社团；
-
如果仍有多个社团可以分配，则按提交参加申请的顺序分配。
-
因为蒜协大部分成员都去播种过冬的大蒜了，所以需要在烹饪和炼丹部打蒜蓉的你协助负责人计算一下每个社团能分到几个格子的摊位。
输入格式
输入的第一行包含一个两个正整数
T
(
1
≤
T
≤
10
5
)
,
H
(
1
≤
H
≤
10
9
)
T(1\\le T \\le 10^5), H(1\\le H \\le 10^9)
T(1≤T≤105),H(1≤H≤109)，分别表示社团的数量和场地格子的数量。
输入的第二行包含
T
T
T 个正整数
u
1
,
u
2
,
⋯
,
u
T
(
1
≤
u
i
≤
10
9
)
u_1, u_2, \\cdots,u_T(1\\le u_i\\le 10^9)
u1,u2,⋯,uT(1≤ui≤109)，分别表示每个社团的贡献。
输出格式
输出一行
T
T
T 个整数，其中第
i
i
i（
1
≤
i
≤
T
1\\le i\\le T
1≤i≤T） 个整数表示第
i
i
i 个社团的摊位包括几个格子。
输入输出样例 #1
输入 #1
4 7
2 1 4 3
输出 #1
1 1 3 2
输入输出样例 #2
输入 #2
9 27
801 919 210 101 417 713 304 613 921
输出 #2
4 4 2 1 3 4 2 3 4
说明/提示
题目来源
来自 2025 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2025）初赛。
题解等资源可在 https://gitlink.org.cn/thusaa/thupc2025pre/tree/master 查看。
C++实现
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=100005;
struct Node{
int id,cnt;
double val,st;
bool operator<(const Node &rhs) const{
if(val!=rhs.val)return val<rhs.val;
if(cnt==0^rhs.cnt==0)return cnt;
if(st!=rhs.st)return st<rhs.st;
return id>rhs.id;
}
}a[N];
int ans[N];
int main(){
int n,k;
cin>>n>>k;
priority_queue<Node> q;
for(int i=1;i<=n;i++){
double x;
cin>>x;
q.push({i,0,x,x});
}
while(!q.empty()&&k){
Node u=q.top();
if(u.val<2)break;
q.pop();
u.cnt++;
u.val/=2;
q.push(u);
k—;
}
while(!q.empty()){
Node u=q.top();
q.pop();
a[u.id]=u;
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
ans[a[i].id]=a[i].cnt+k/n+(i>n–k%n);
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<' ';
}
return 0;
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
