本題同ZeroJudge高中部網站的b107。
必須認清題目需求。
1.一開始分成五大類。
2.五大類裡面,手上的刀劍斧,弓弩,棍棒杖,盾沒有顏色,故不用排,但要排等級。包含手套等其他的裝備,沒有等級,但要排顏色。
3.每一個裝備都要排名字。
4.名字順序是短 < 長。同樣長度則 A < a <B < b <C < c ...... < Z < z。和C++字串的lib的compare()不一樣。
5.實作快速排序是比較方便做if分支不同情況的。
#include <iostream>
#include <vector>
using namespace std;
const unsigned int eSIZE = 5; // equipment size
struct equip
{
vector< vector<string> > equip_n;
vector< vector<unsigned int> > equip_v;
};
inline char compare_str(const string &sa, const string &sb)
{
if (sa.length() > sb.length())
return(1);
else if (sa.length() < sb.length())
return(-1);
for (unsigned int i = 0; i != sa.length(); ++i)
{
if ((sa[i] & 31) > (sb[i] & 31))
return(1);
else if ((sa[i] & 31) < (sb[i] & 31))
return(-1);
else
{
if (sa[i] > sb[i])
return(1);
else if (sa[i] < sb[i])
return(-1);
}
}
return(0);
}
void quicksort(equip &A, int left, int right, const unsigned int &value)
{
if (left < right)
{
int i = right + 1, j = left;
if (value != 3)
{
while (true)
{
while (i > j && A.equip_v[--i][value] > A.equip_v[left][value])
;
while (i > j && A.equip_v[++j][value] < A.equip_v[left][value])
;
A.equip_v[i].swap(A.equip_v[j]);
A.equip_n[i].swap(A.equip_n[j]);
if (i == j)
break;
}
A.equip_v[left].swap(A.equip_v[j]);
A.equip_n[left].swap(A.equip_n[j]);
quicksort(A, j + 1, right, value);
quicksort(A, left, j - 1, value);
}
else
{
while (true)
{
while (i > j && compare_str(A.equip_n[--i][0], A.equip_n[left][0]) > 0)
;
while (i > j && compare_str(A.equip_n[++j][0], A.equip_n[left][0]) < 0)
;
A.equip_v[i].swap(A.equip_v[j]);
A.equip_n[i].swap(A.equip_n[j]);
if (i == j)
break;
}
A.equip_v[left].swap(A.equip_v[j]);
A.equip_n[left].swap(A.equip_n[j]);
quicksort(A, j + 1, right, value);
quicksort(A, left, j - 1, value);
}
}
}
int main(void)
{
cout << flush;
ostream *old_tie = cin.tie();
cin.tie(0);
ios::sync_with_stdio(false);
const unsigned int tSIZE = 12;
const string type[tSIZE] = {"hat", "earring", "sword", "bow",
"bastinado", "targe", "glove", "clothes",
"cape", "pant", "skirt", "shoe"};
const unsigned int type_value[tSIZE] = {0, 1, 10, 11,
12, 13, 14, 20,
21, 30, 31, 40};
const unsigned int cSIZE = 8;
const string color[cSIZE] = {"W", "P", "B", "R",
"Y", "G", "K", "U"};
const unsigned int color_value[cSIZE] = {0, 1, 2, 3,
4, 5, 6, 7};
int cases;
cin >> cases;
while (cases--)
{
unsigned int item;
cin >> item;
cin.get();
if (!item)
cout << "--------\n";
else
{
vector<equip> equip_vec(eSIZE);
for (unsigned i = 0; i != eSIZE; ++i)
equip_vec[i].equip_n.clear(), equip_vec[i].equip_v.clear();
for (unsigned int i = 0; i != item; ++i)
{
vector<string> name(2); // 0 is name, 1 is AA
cin >> name[0]; // name
string s;
s.clear();
for (unsigned int j = 0, k = 0; k != 2 && j != name[0].length(); ++j)
if (name[0][j] <= 'Z')
{
s.append(1, name[0][j]);
++k;
}
name[1] = s;
vector<unsigned int> value(3); // 0 is type, 1 is color, 2 is level
unsigned int index = 0;
cin >> s; // type
for (unsigned int j = 0; j != tSIZE; ++j)
if (!s.compare(type[j]))
{
value[0] = type_value[j] % 10;
index = type_value[j] / 10;
break;
}
cin >> s; // color
for (unsigned int j = 0; j != cSIZE; ++j)
if (!s.compare(color[j]))
{
value[1] = color_value[j];
break;
}
cin >> value[2]; // level
cin.get();
equip_vec[index].equip_n.push_back(name);
equip_vec[index].equip_v.push_back(value);
}
for (unsigned int i = 0; i != eSIZE; ++i)
{
int size = equip_vec[i].equip_n.size();
if (i != 4)
quicksort(equip_vec[i], 0, size - 1, 0);
int l1, l2, r1, r2;
for (l1 = 0, r1 = 0; r1 != size; ++r1)
if (equip_vec[i].equip_v[l1][0] != equip_vec[i].equip_v[r1][0])
{
if (!(i == 1 && equip_vec[i].equip_v[l1][0] != 4))
{
quicksort(equip_vec[i], l1, r1 - 1, 1);
for (l2 = l1, r2 = l1; r2 != r1; ++r2)
{
if (equip_vec[i].equip_v[l2][1] != equip_vec[i].equip_v[r2][1])
{
quicksort(equip_vec[i], l2, r2 - 1, 3);
l2 = r2;
}
}
if (r2 - l2 > 1)
quicksort(equip_vec[i], l2, r2 - 1, 3);
l2 = r2;
}
else // "sword", "bow", "bastinado", "targe"
{
quicksort(equip_vec[i], l1, r1 - 1, 2);
for (l2 = l1, r2 = l1; r2 != r1; ++r2)
{
if (equip_vec[i].equip_v[l2][2] != equip_vec[i].equip_v[r2][2])
{
quicksort(equip_vec[i], l2, r2 - 1, 3);
l2 = r2;
}
}
if (r2 - l2 > 1)
quicksort(equip_vec[i], l2, r2 - 1, 3);
l2 = r2;
}
l1 = r1;
}
if (r1 - l1 > 1)
{
if (!(i == 1 && equip_vec[i].equip_v[l1][0] != 4))
{
quicksort(equip_vec[i], l1, r1 - 1, 1);
for (l2 = l1, r2 = l1; r2 != r1; ++r2)
{
if (equip_vec[i].equip_v[l2][1] != equip_vec[i].equip_v[r2][1])
{
quicksort(equip_vec[i], l2, r2 - 1, 3);
l2 = r2;
}
}
if (r2 - l2 > 1)
quicksort(equip_vec[i], l2, r2 - 1, 3);
l2 = r2;
}
else // "sword", "bow", "bastinado", "targe"
{
quicksort(equip_vec[i], l1, r1 - 1, 2);
for (l2 = l1, r2 = l1; r2 != r1; ++r2)
{
if (equip_vec[i].equip_v[l2][2] != equip_vec[i].equip_v[r2][2])
{
quicksort(equip_vec[i], l2, r2 - 1, 3);
l2 = r2;
}
}
if (r2 - l2 > 1)
quicksort(equip_vec[i], l2, r2 - 1, 3);
l2 = r2;
}
l1 = r1;
}
}
for (unsigned int i = 0; i != eSIZE; ++i)
{
unsigned int size = equip_vec[i].equip_n.size();
for (unsigned int j = 0; j != size; ++j)
{
cout << equip_vec[i].equip_n[j][1];
if (((j + 1) & 3) == 0)
cout.put('\n');
}
unsigned int spaces = size & 3;
if (spaces)
{
for (unsigned int j = 0; j != 4 - spaces; ++j)
{
cout.put('_');
cout.put('_');
}
cout.put('\n');
}
}
cout << "--------\n";
}
}
ios::sync_with_stdio(true);
cin.tie(old_tie);
cout << flush;
return(0);
}