Sicily-1006

开发者智越技术 2022年11月10日

0 收藏 842 点赞 4,031 浏览 1244 个字

一．题意

　　　这道题就是考排列组合吧，再来就是比较一下字符的下标算一下两个ranking的距离。然后我总结了一个排列和一个组合的实现方法，这道题直接用的是stl　　　　里面的next_permutation，注意要排好序，好像也有一个previous_permutation的方法的，不过没用过。

二．过程

算出120情况，还好这里是5个字符
然后写出计算两个ranking的函数。
然后就是算最小值啦。

三．

 //
 //  main.cpp
 //  sicily-1006
 //
 //  Created by ashley on 14-10-7.
 //  Copyright (c) 2014年 ashley. All rights reserved.
 // #include <iostream>
 #include <algorithm>
 #include <stack>
 using namespace std;
 string permutations[];
 string guess[];
 //获得120种ABCDE的排列情况
 void getPermutaions()
 {
     int counter = ;
     string cha = "ABCDE";
     string adding;
     do {
         adding = cha;
         permutations[counter++] = adding;
     } while (next_permutation(cha.begin(), cha.begin() + ));
 }
 //查找一个字符在字符串里面的下标
 int finding(char c, string s)
 {
     int len = (int)s.length();
     for (int i = ; i < len; i++) {
         if (s[i] == c) {
             return i;
         }
     }
     return ;
 }
 //计算两个字符串的差值
 int compare(string ss, string r)
 {
     int len = (int)ss.length();
     int sum = ;
     for (int i = ; i < len - ; i++) {
         for (int j = i + ; j < len; j++) {
             if (finding(r[i], ss) > finding(r[j], ss)) {
                 sum++;
             }
         }
     }
     return sum;
 }
 int main(int argc, const char * argv[])
 {
     int cases;
     getPermutaions();
     while (cin >> cases) {
         if (cases == ) {
             break;
         }
         int min =  * cases;
         int key = -;
         for (int i = ; i < cases; i++) {
             cin >> guess[i];
         }
         for (int i = ; i < ; i++) {
             int diff = ;
             for (int j = ; j < cases; j++) {
                 diff = diff + compare(guess[j], permutations[i]);
             }
             if (diff < min) {
                 key = i;
                 min = diff;
             }
         }
         cout << permutations[key] << " is the median ranking with value " << min << "." << endl;
     }
     return ;
 }