2022 RoboCom 世界机器人开发者大赛-本科组（省赛）RC-u4 攻略分队_7-107 剪切粘贴 分数 15 作者 dai, longao 单位 杭州百腾教育科技有限公司 使用

RC-u4 攻略分队
分数 25
作者 DAI, Longao
单位 杭州百腾教育科技有限公司
副本是游戏里的一个特色玩法，主要为玩家带来装备、道具、游戏资源的产出，满足玩家的游戏进程。

在 MMORPG《最终幻想14》里，有一个攻略人数最大达到 56 人的副本“巴尔德西昂兵武塔”，因为有在副本里死亡不能复活、机制比较整蛊等特点，一度被玩家视作洪水猛兽。

在副本的开始，我们会遇到第一个难关：攻略的玩家要分为两组，同时讨伐副本 BOSS “欧文”和“亚特”。

已知以下信息：

玩家会组成 6 支队伍进入副本，其中第 i 队有 V
i
​
位玩家（i=1,⋯,6）。
每支队伍可能会有一些特殊角色：MT（主坦克）、工兵（负责探测陷阱）和指挥（负责指挥玩家）。
我们的任务是合理安排玩家的分组，以最大程度增加副本通过概率。分组的原则如下：

要将所有队伍分成 2 组，每支队伍必须且仅属于其中一组；
每组必须有至少一个 MT（主坦克）。
如果满足上述原则的分组方案不唯一，则按照下列规则确定唯一解：

优先选择每组有至少一个指挥和至少一个工兵的方案；
如果规则 1 无法满足，则优先选择每组至少有一个指挥的方案；
如果所有方案都不满足规则 2，或经过前 2 个规则筛选后，分组方案仍不唯一，则选择两边人数尽可能接近（即两边人数差尽可能小）的方案；
如果满足规则 3 的方案还不唯一，选择讨伐“欧文”的人数比讨伐“亚特”的人数更多的方案；
如果满足规则 4 的方案还不唯一，选择讨伐“欧文”的队伍编号方案中最小的一个。

本题就请你给出满足所有分组原则的分配方案。

输入格式:
输入第一行给出 6 支队伍的玩家数量，即 6 个非负整数 V
队伍人数为 0 时表示队伍不存在。

随后 6 行，按队伍编号顺序，每行给出一支队伍的特殊角色，格式为 ABC，其中 A 对应 MT，B 对应工兵，C 对应指挥。三种角色对应取值 0 或 1，0 表示没有该角色，1 表示有。

注：由于可能存在一人兼任多个特殊角色的情况，所以一支队伍中的特殊角色数量有可能大于该队伍的玩家数量。

输出格式:
输出分两行，第一行输出讨伐“欧文”的队伍编号，第二行输出讨伐“亚特”的队伍编号。同一行中的编号按升序输出，以 1 个空格分隔，行首尾不得有多余空格。

如果不存在合法的方案，输出GG。

输入样例1:
6 8 7 5 3 0
010
101
110
001
111
000
输出样例1:
2 3
1 4 5
输入样例2:
6 8 7 5 3 0
010
101
010
001
011
000
输出样例2:
GG
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#pragma GCC optmize(3)
#pragma GCC optmize(2)
using namespace std;

int num[8],flag=-1,re=10000,l=-1;
bool st[8];
int cnt[8][3];
// mt, gong, zhihui
vector<int>a,b,s;

bool check(vector<int>&x,vector<int>&y)  
{   
    if(x.empty()||y.empty())return false;
    
    int res=-1,r1=0,r2=0;
    static int q[3],e[3];
    memset(q,0,sizeof q);memset(e,0,sizeof e);
    for(int i=0;i<x.size();i++)
    {
        int u=x[i];
        r1+=num[u];
        
        for(int j=0;j<3;j++)
        {
            if(cnt[u][j])q[j]++;    
        }
    }
    for(int i=0;i<y.size();i++)
    {
        int u=y[i];
        r2+=num[u];
        for(int j=0;j<3;j++)
        {
            if(cnt[u][j])e[j]++;    
        }
    }
 
    if(q[0]&&e[0]&&q[1]&&q[2]&&e[1]&&e[2]){
        if(flag<2){
            flag=2;
            re=abs(r1-r2);
            l=r1-r2>0?1:0;
            return true;
        }
        res=2;
    }
    else if(q[0]&&e[0]&&e[2]&&q[2]){
        if(flag<1){
            flag=1;
            re=abs(r1-r2);
            l=r1-r2>0?1:0;
            return true;
        }
        res=1;
    }
     else if(q[0]&&e[0]){
        if(flag<0){
            re=abs(r1-r2);
            l=r1-r2>0?1:0;
            flag=0;
            return true;
        }
        res=0;
    }
    else return false;
    
    if(res==flag)
    {
        if(abs(r1-r2)<re){
            
            re=abs(r1-r2);
            l=r1-r2>0?1:0;
            return true;
        }
        else if(abs(r1-r2)==re)
        {

            int j=r1-r2>0?1:0;
            if(l<j){
                l=j;
                return true;
            }
            else if(l==j){
                return x<a;
            }
        }
    }
 
    return false;
}

int main(){
   
    for(int i=1;i<=6;i++){
    scanf("%d",&num[i]);
    if(num[i]!=0)s.push_back(i);
    }
 
    for(int i=1;i<=6;i++)
    {
        string x;
        cin>>x;
        for(int j=0;j<3;j++)
        cnt[i][j]=x[j]-'0';
    }
    int t=s.size();
    
    for(int i=1;i<1<<t;i++){
        vector<int>x,y;   
        for(int j=0;j<s.size();j++)
        {   
            if(i>>j&1)
            x.push_back(s[j]);
            else y.push_back(s[j]);
        }
        if(check(x,y))a=x,b=y;
    } 
    if(!a.size()||!b.size())return puts("GG"),0;
    for(int i=0;i<a.size();i++){
        if(i)printf(" ");
        cout<<a[i];
    }
    cout<<endl;
    for(int i=0;i<b.size();i++){
        if(i)printf(" ");
        cout<<b[i];
    }
    exit(0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134