题解：P16441 [XJTUPC 2026] 直播获奖

Sunrise_up · 2026-05-10 23:41:09 · 题解

求点赞 qwq！

不懂可问。

思路

直接模拟，没什么好说的。

显然用结构体维护。

对于每一轮：

• 清空应该清空的东西。
• 判断是否 |S|\le 4，若是的话直接输出。
• 把 S 全部丢入一个数组 v，将 v 按成绩 z 降序排序。
• 按照规则选出 A，用一个数组 vis 维护已进入省队的人，用桶数组 t 维护当前省队中每个公会已入选的人数，然后输出 A。
• 清空 v，再把 S \setminus A 丢入 v，这里用到了 vis。
• 按照规则选出 B，这里用到了 t，然后输出 B。

注意：

• 是该公会在省队中的当前人数而不是该公会在 B 队中的当前人数。
• 记得清空。

代码

时间复杂度 O(n^2)。

#include<bits/stdc++.h>
using namespace std;
const int N=101;
int n,t[N];
bool vis[N];
struct node{int x,y,z,id;}p[N];
bool cmp(node s,node t){return s.z>t.z;}
bool cmp2(node s,node t){return s.id<t.id;}
vector<node> v,ans;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y>>p[i].z,p[i].id=i;
    for(int i=1;i<=n;i++){
        v.clear(),ans.clear(),memset(t,0,sizeof(t)),memset(vis,0,sizeof(vis));
        if(i<=4){
            for(int j=1;j<=i;j++)cout<<j<<' ';
            cout<<'\n';
            continue;
        }
        for(int j=1;j<=i;j++)v.push_back(p[j]);
        sort(v.begin(),v.end(),cmp);
        int all=0;
        for(int j=0;j<5;j++)all+=v[j].x;
        for(int j=0;j<4;j++)ans.push_back(v[j]),vis[v[j].id]=1;
        if(all==5||all==0){
            int x=(all==5);
            for(auto u:v){
                if(u.x!=x){
                    ans.push_back(u),vis[u.id]=1;
                    break;
                }
            }
        }else ans.push_back(v[4]),vis[v[4].id]=1;
        sort(ans.begin(),ans.end(),cmp2);
        for(auto k:ans)cout<<k.id<<' ',t[k.y]++;
        ans.clear(),v.clear();
        for(int j=1;j<=i;j++)if(!vis[j])v.push_back(p[j]);
        sort(v.begin(),v.end(),cmp);
        for(auto k:v){
            if(ans.size()==12)break;
            if(t[k.y]>=5)continue;
            t[k.y]++,ans.push_back(k);
        }
        sort(ans.begin(),ans.end(),cmp2);
        for(auto k:ans)cout<<k.id<<' ';
        cout<<'\n';
    }
}