列印

請 登入 或 註冊帳號.
一小時 一天 一週 一個月 永遠
請輸入帳號, 密碼以及預計登入時間

[bleed1979]

本題同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);
}




[david942j]

提供個人感覺比較簡潔的程式碼XD

代碼: [選擇]

#include <iostream>
typedef struct {char s[31];int a,b,c,d;}M;
M t[40];
int cha(int p)
{
switch(p)
{
case 0:
case 1:return 0;
case 2:
case 3:
case 4:
case 5:
case 6:return 1;
case 7:
case 8:return 2;
case 9:
case 10:return 3;
case 11:return 4;
}
}
int chb(char *s)
{
switch(s[0])
{
case 'h':return 0;
case 'e':return 1;
case 's':
if(s[1]=='w')return 2;
if(s[1]=='k')return 10;
return 11;
case 'b':
if(s[1]=='o')return 3;
return 4;
case 't':return 5;
case 'g':return 6;
case 'c':
if(s[1]=='l')return 7;
return 8;
case 'p':return 9;
}
}
int chc(char c)
{
switch(c)
{
case 'W':return 0;
case 'P':return 1;
case 'B':return 2;
case 'R':return 3;
case 'Y':return 4;
case 'G':return 5;
case 'K':return 6;
default:return -1;
}
}
void out(char *s)
{
int i=0;
while(s[i]>='a')i++;
printf("%c",s[i]),i++;
while(s[i]>='a')i++;
printf("%c",s[i]);
}
int com(M x,M y)
{
if(x.a>y.a)return 1;
if(x.a<y.a)return 0;
if(x.b>y.b)return 1;
if(x.b<y.b)return 0;
if(x.c!=-1)
{
if(x.c>y.c)return 1;
if(x.c<y.c)return 0;
}
else
{
if(x.d>y.d)return 1;
if(x.d<y.d)return 0;
}
int i,m=strlen(x.s),n=strlen(y.s);
for(i=0;i<m&&i<n;i++)
if(x.s[i]>y.s[i])
{
if(x.s[i]<='Z')
return 1;
if(y.s[i]>='a')
return 1;
return x.s[i]-32>=y.s[i];
}
else if(x.s[i]<y.s[i])
{
if(x.s[i]>='a')
return 0;
if(y.s[i]<='Z')
return 0;
return x.s[i]+32>y.s[i];
}
if(i==n)return 1;
return 0;
}
int main()
{
int n,T,i,j,f;
char c[20];
M tmp;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%s%s",t[i].s,c),t[i].b=chb(c),t[i].a=cha(t[i].b),scanf("%s%d",c,&t[i].d),t[i].c=chc(c[0]);
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(com(t[i],t[j]))
tmp=t[i],t[i]=t[j],t[j]=tmp;
out(t[0].s),f=1;
for(i=1;i<n;i++)
{
if(t[i].a!=t[i-1].a)
{
for(j=0;j<4-f;j++)
printf("__");
printf("\n"),f=0;
}
if(f==4)printf("\n"),f=0;
out(t[i].s),f++;
}
for(j=0;j<4-f;j++)
printf("__");
printf("\n--------\n");
}
}


[annielin]

怎麼按字典順序排序= =
以前沒排過
講寫法就好了
程式碼不一定看得懂
感謝

[lini]

怎麼按字典順序排序= =
以前沒排過
講寫法就好了
程式碼不一定看得懂
感謝

1. 比較長度 一樣則 ↓
2. for迴圈 兩個字串逐一字元比較(方式可以盡情發揮創意 ... XD )
　我覺得比較簡單的寫法是
　　a. 兩個字原都轉成小寫比較 (tolower)
　　b. 如果一樣看誰是大寫 (isupper)
　　c. 如果同樣都是大寫或小寫 則for迴圈往下繼續比較

[sagit]

怎麼按字典順序排序= =
以前沒排過
講寫法就好了
程式碼不一定看得懂
感謝

1. 比較長度 一樣則 ↓
2. for迴圈 兩個字串逐一字元比較(方式可以盡情發揮創意 ... XD )
　我覺得比較簡單的寫法是
　　a. 兩個字原都轉成小寫比較 (tolower)
　　b. 如果一樣看誰是大寫 (isupper)
　　c. 如果同樣都是大寫或小寫 則for迴圈往下繼續比較

我的作法是先把這個名稱的每一個字元先做轉換，
而它只有A~Z、a-z這52種字元，因此可以用下面的轉換方式：

代碼: [選擇]

if (s[k]<='Z') // 大寫
    s[k]=(s[k]-'A')*2+32;
else // 小寫
    s[k]=(s[k]-'a')*2+33;
其中 s[k] 代表裡面的一個字元，
這樣轉換的好處是，因為這個名稱要比較很多次，
你只要先轉換一次，之後就可以直接用內建的字串比較函數來處理。
不過，因為答案要印出原本名稱的前兩個大寫字母，
所以要再增加一個欄位記錄這個東西。