攻略分队（java实现）

攻略分队（java实现）

副本是游戏里的一个特玩法，主要为玩家带来装备、道具、游戏资源的产出，满足玩家的游戏进程。

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

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

已知以下信息：

1. 玩家会组成 6 支队伍进入副本，其中第 i 队有 Vi​ 位玩家（i=1,⋯,6）。
2. 每支队伍可能会有一些特殊角：MT（主坦克）、工兵（负责探测陷阱）和指挥（负责指挥玩家）。

我们的任务是合理安排玩家的分组，以最大程度增加副本通过概率。分组的原则如下：

1. 要将所有队伍分成 2 组，每支队伍必须且仅属于其中一组；
2. 每组必须有至少一个 MT（主坦克）。

如果满足上述原则的分组方案不唯一，则按照下列规则确定唯一解：

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

注：一个队伍编号方案 A={a1​<⋯<am​} 比 B={b1​<⋯<bn​} 小，当且仅当存在 1≤k≤min(m,n) 使得 ai​=bi​ 对所有 0<i<k 成立，且 ak​<bk​。

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

输入格式：

输入第一行给出 6 支队伍的玩家数量，即 6 个非负整数 Vi​ (0≤Vi​≤8,1≤i≤6)。队伍人数为 0 时表示队伍不存在。

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

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

输出格式：

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

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

输入样例1：

6 8 7 5 0
010
101
110
001
111
000

输出样例1：

2
1 4 5 

输入样例2：

6 8 7 5 0
010
101
010
001
011
000 

输出样例2：

GG 

代码长度限制                                                                                                                  16 KB

时间限制                                                                                                                        400 ms

内存限制                                                                                                                         64MB 

题解：

这道题好像大家都觉得比较简单，但是我觉得并不简单。。。这个解法是得益于这个博主的题解。6个队伍我们要随机分配到两个集合中（欧文和亚特），我们要做的是选出一个最优方案满足题目中的原则和5条规则。其实每次给出的数据数量都是固定的，每次都是分配到两个集合，每次都有6支队伍，那我们就可以列举出所有队伍组合，然后通过原则筛选，筛选后的再通过5个规则进行排序，在同等规则一样的话就用下个规则继续比！最后排序完第一个就是最优方案！说实话我觉得这个思路是真的妙啊。现在第一件事就是求出所有队伍组合，那有多少种队伍组合呢？一共有种，根据题目的要求，每个集合中至少有一支队伍，所以集合里最少有1支队伍，最多有5支队伍，这是个组合问题，相信大家都很容易理解。现在有个问题就是，我们怎么求出这62种组合？这是本题解的精华所在，我现在也没搞懂它的原理所在。

Set<String> set = new LinkedHashSet<String>();for (int i = 1; i <= 62; i) {StringBuilder sb = new StringBuilder();for (int j = 1; j <= 6; j) {if (((1<<(j-1))&i) != 0) {sb.append(j);}}set.add(());}

这段代码的作用就是把6个队伍分配到2个集合的62种分配方案全部求出来，最后都装到set里。其中((1<<(j-1))&i) != 0就是精华所在，我不知道为什么，我对位运算不熟，不知道这个用法是哪个知识点，总之它就是可以每次过滤出不一样的方案，经过这62次循环，我们刚好得到62个方案，我还特意用set去重，实际上每次都是新的方案，没有重复！我们排下序看下set里面的情况：

可以看到，刚好62个，每个都不重复，而且也是满足至少有一支队伍的要求，所以最长的不会超过5。有知道这个用法是怎么回事的朋友请教教我，我真的好想知道是怎么回事。

现在我们求出了62种方案，就可以对这些方案进行过滤了。为了方便排序，我把方案抽象为一个类，类里面的属性都是为了判断是否满足5个规则。然后在类里写了排序规则，就是题目的5个规则的体现，具体见代码。 

我们先按原则进行排除，符合原则的加入一个集合进行排序，最后排完序第一个就是最优解。如果集合里一个方案也没有，就输出GG。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collecti;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;public class Main {public static void main(String[] args) { InputReader in = new InputReader();List<Scheme> schemes = new ArrayList<Scheme>();//用来存放进行排序的方案int[][] ranks = new int[7][4];//二维数组保存队伍信息，每一行就是一个队伍for (int i = 1; i < 7; i) ranks[i][0] = ();//0列保存队伍人数for (int i = 1; i < 7; i) {String specialRoles = ();ranks[i][1] = (0) - 48;//1列保存队伍的MT数量ranks[i][2] = (1) - 48;//2列保存队伍的工兵数量ranks[i][] = (2) - 48;//列保存队伍的指挥数量}for (int i = 1; i <= 62; i) {//这个循环用来求所有方案Scheme scheme = new Scheme(); = new LinkedList<Integer>();scheme.artTeamum = new LinkedList<Integer>();for (int j = 1; j < 7; j) {//这个循环就是具体确定这个方案包含哪些队伍if (ranks[j][0] == 0) //通过题目样例可以知道队伍人数为0直接不要continue;if (((1 << (j - 1)) & i) != 0) {//要么给欧文，要么给亚特.add(j); = ranks[j][0]; |= ranks[j][1];//我们只需要知道为不为0，所以可以用|= |= ranks[j][2]; |= ranks[j][];} else {scheme.artTeamum.add(j);scheme.artPeoum = ranks[j][0];scheme.artMT |= ranks[j][1];scheme.artEng |= ranks[j][2];scheme.artCom |= ranks[j][];}}//通过原则进行筛选，不符合原则的不能加入集合进行排序if (.size() == 0 || scheme.artTeamum.size() == 0 ||  == 0 || scheme.artMT == 0) continue;//计算方案的其他属性scheme.difference = Math.abs( - scheme.artPeoum);//欧文和亚特的人数差scheme.greaterThan =  > scheme.artPeoum ? true : false;//欧文人数是否多于亚特scheme.MTBoth = ( & scheme.artMT) != 0 ? true : false;//欧文和亚特是否都有 = ( & scheme.artEng) != 0 && ( & scheme.artCom) != 0 ? true : false;//欧文和亚特是否都有工兵和指挥schemeBoth = ( & scheme.artCom) != 0 ? true : false;//欧文和亚特是否都有指挥schemes.add(scheme);//最后加入集合等待排序}Collecti.sort(schemes);//进行排序！if (schemes.size() > 0) {//如果集合里一个都没有，说明都不符合原则，输出GGint i = 0;for (int rank : schemes.get(0).owenTeamum) {//输出欧文if (i == 0) {print(rank);i;}else {print(   rank);}}println();i = 0;for (int rank : schemes.get(0).artTeamum) {//输出亚特if (i == 0) {print(rank);i;}else {print(   rank);}}} else {print(GG);}}}class Scheme implements Comparable<Scheme>{//方案类，每个方案都包含一个欧文集合和一个亚特集合public int owenPeoum;//欧文组的总人数public int artPeoum;//亚特组的总人数public LinkedList<Integer> owenTeamum;//欧文组的队伍编号public LinkedList<Integer> artTeamum;public int owenMT;//欧文组的主坦克数量public int artMT;public int owenEng;//欧文组的工兵数量public int artEng;public int owenCom;//欧文组的指挥数量public int artCom;public int difference;//两组人数差public boolean greaterThan;//true:欧文组人数大于亚特组人数，反之falsepublic boolean MTBoth;//true:两组都有主坦克，反之falsepublic boolean engComBoth;//true:两组都有工兵和指挥，反之falsepublic boolean comBoth;//true:两组都有指挥，反之falsepublic int compareTo(Scheme o) {if ( && !) {//规则1，两组集合都有工兵和指挥的方案排在前面return -1;//返回-1才是排在前面哦，返回1是排在后面}else if ( == ) {//如果都一样进入规则2if (thisBoth && !oBoth) {//规则2，两组集合都有指挥的方案排在前面return -1;}else if ( == ) {//如果都一样进入规则if (this.difference < o.difference) {//规则，人数差小的方案排在前面return -1;}else if (this.difference == o.difference) {//如果都一样进入规则4if (this.greaterThan && !o.greaterThan) {//规则4，欧文比亚特人数多的方案排在前面return -1;}else if (this.greaterThan == o.greaterThan) {//如果两个方案都是欧文比亚特人数多或者少那就进入规则5//规则5可能不太好理解，就是两个方案的欧文队伍编号一个一个比，谁先比对方小的就算比较小for (int i = 0; i < size() && i < size(); i) if (get(i) != get(i)) return get(i) - get(i);//因为是两个方案，所以可能出现1 2，1 2 这种情况，这个时候按队伍数少的算小return size() - size();}else {return 1;}}else {return 1;}}else {return 1;}}else {return 1;}}}class InputReader{BufferedReader buf;StringTokenizer tok;public InputReader() {buf = new BufferedReader(new InputStreamReader(System.in));}boolean hat() {while (tok == null || !tok.hasMoreElements()) {try {tok = new StringTokenizer(buf.readLine());} catch (IOException e) {return false;}}return true;}String next() {if (hat()) return ();return null;}int nextInt() {return Integer.parseInt(next());}String nextLine() throws IOException {return buf.readLine();}
}