<h3>Problem Statement</h3><p>You are given a permutation <var>P=(P _ 1,P _ 2,\ldots,P _ N)</var> of <var>(1,2,\ldots,N)</var>.</p> <p>Find the following value for all <var>i\ (1\leq i\leq N)</var>:</p> <ul> <li><var>D _ i=\displaystyle\min_{j\neq i}\left\lparen\left\lvert P _ i-P _ j\right\rvert+\left\lvert i-j\right\rvert\right\rparen</var>.</li> </ul>

你被给了一个排列 P=(P1,P2,...,PN) 的 (1,2,...,N)。

对于所有的 i (1≤i≤N)，求出以下值：

D i=min(|Pi−Pj| |i−j|) (j≠i)

这个问题的意思是，你需要求出对于每个 i，它所对应的 D i 值是多少。D i 表示的是在排列 P 中，对于第 i 个位置，所有与它不同位置的 |Pi−Pj|×|i−j| 的最小值。

相关问题

#include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N = 10; int n, m; int a[N]; int main() { cout << "请输入结点数：" << endl; while (cin >> n >> m) //输入图1、2的结点数 { if (m != n) { cout << "两图不同构！！！" << endl; continue; } //根据结点数n、m，动态生成两个二维数组来存图（使用邻接矩阵的方式） vector<int> w1(n + 1, 0); vector<vector<int> > g1(n + 1, w1); vector<int> w2(m + 1, 0); vector<vector<int> > g2(m + 1, w2); for (int i = 1; i <= n; i++) a[i] = i; //初始化a数组 for (int i = 1; i <= n; i++) //输入图1的邻接矩阵 for (int j = 1; j <= n; j++) cin >> g1[i][j]; for (int i = 1; i <= m; i++) //输入图2的邻接矩阵 for (int j = 1; j <= m; j++) cin >> g2[i][j]; //全排列 do { bool f = 0; int temp[N][N]; memset(temp, 0, sizeof temp); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { temp[i][j] = g1[a[i]][a[j]]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (temp[i][j] != g2[i][j]) { f = 1; break; } } if (f == 1) break; } if (f == 0) cout << "两图同构^-^" << endl; } while (next_permutation(a + 1, a + 1 + n)); cout << "两图不同构！！！" << endl; } return 0; }简化的完整代码

这是一个判断两个图是否同构的程序，输入两个图的邻接矩阵，通过枚举两个图的节点的排列顺序，判断它们是否同构。如果是同构的，则输出"两图同构^-^"，否则输出"两图不同构！！！"。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 10;

int n, m;
int a[N];

int main() {
    cout << "请输入结点数：" << endl;
    while (cin >> n >> m) { //输入图1、2的结点数
        if (m != n) {
            cout << "两图不同构！！！" << endl;
            continue;
        }
        //根据结点数n、m，动态生成两个二维数组来存图（使用邻接矩阵的方式）
        vector<int> w1(n + 1, 0);
        vector<vector<int> > g1(n + 1, w1);
        vector<int> w2(m + 1, 0);
        vector<vector<int> > g2(m + 1, w2);
        for (int i = 1; i <= n; i++) a[i] = i; //初始化a数组
        for (int i = 1; i <= n; i++) //输入图1的邻接矩阵
            for (int j = 1; j <= n; j++)
                cin >> g1[i][j];
        for (int i = 1; i <= m; i++) //输入图2的邻接矩阵
            for (int j = 1; j <= m; j++)
                cin >> g2[i][j];
        //全排列
        do {
            bool f = 0;
            int temp[N][N];
            memset(temp, 0, sizeof temp);
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    temp[i][j] = g1[a[i]][a[j]];
                }
            }
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (temp[i][j] != g2[i][j]) {
                        f = 1;
                        break;
                    }
                }
                if (f == 1) break;
            }
            if (f == 0) cout << "两图同构^-^" << endl;
        } while (next_permutation(a + 1, a + 1 + n));
        cout << "两图不同构！！！" << endl;
    }
    return 0;
}

优化改进以下代码#include <iostream> #include <fstream> #include <string> #include <vector> #include <algorithm> #include <iterator> using namespace std; typedef istream_iterator<string> string_input; void welcome() { cout << "******************* 变位词查找系统*********************\n" << "在词典中找出给定的字符串的所有变位词" << endl; } void readDict(vector<string> & dictionary) { cout << "首先，请输入词典的文件名称：" << endl; string dictionary_name; cin >> dictionary_name; ifstream ifs(dictionary_name.c_str()); if (!ifs.is_open()) { cerr << "异常：文件"<< dictionary_name << "没有找到 " << endl; exit(1); } cout << "词典读入中 ..." << flush; copy(string_input(ifs), string_input(), back_inserter(dictionary)); sort(dictionary.begin(),dictionary.end()); cout << "词典包含有 " << dictionary.size() << " 个单词\n\n"; ifs.close(); } void analyseAnagram(const vector<string> & dictionary) { cout << "请输入单词（或任意字母序列）" << endl; for (string_input p(cin); p != string_input(); ++p) { cout << "查找输入单词的变位词中..." << endl; string word = *p; sort(word.begin(), word.end()); bool found_one = false; do { if (binary_search(dictionary.begin(), dictionary.end(), word)) { cout << " " << word ; found_one = true; } } while (next_permutation(word.begin(), word.end())); if (!found_one) cout << " 抱歉，没有找到变位词\n"; cout << "\n请输入下一个单词 " << "(或输入Ctrl+Z终止程序 ) \n" << endl; } } int main() { welcome(); vector<string> dictionary; readDict(dictionary); analyseAnagram(dictionary); system("pause"); return 0; }

以下是一些可以优化改进的建议：

1. 在读入词典文件时，可以使用 ifstream 的构造函数来打开文件，避免在程序中使用 c_str() 函数。可以将以下代码：

ifstream ifs(dictionary_name.c_str());

改为：

ifstream ifs(dictionary_name);

2. 在查找变位词时，可以使用 unordered_set 来存储词典中的单词，这样可以提高查找速度，避免使用 binary_search 函数。可以将以下代码：

sort(dictionary.begin(),dictionary.end());
...
if (binary_search(dictionary.begin(), dictionary.end(), word))

改为：

unordered_set<string> dict_set(dictionary.begin(), dictionary.end());
...
if (dict_set.count(word))

3. 在查找变位词时，可以使用一个 map 来记录每个单词的字母出现次数，避免使用 next_permutation 函数。可以将以下代码：

sort(word.begin(), word.end());
...
do {
    if (binary_search(dictionary.begin(), dictionary.end(), word)) {
        ...
    }
} while (next_permutation(word.begin(), word.end()));

改为：

unordered_map<char, int> word_count;
for (char c : word) {
    ++word_count[c];
}
...
for (const string& dict_word : dictionary) {
    unordered_map<char, int> dict_count;
    for (char c : dict_word) {
        ++dict_count[c];
    }
    if (dict_count == word_count) {
        ...
    }
}

4. 可以添加一些错误处理机制，例如：输入单词为空时，应提示重新输入；输入的文件名不存在时，应提示用户重新输入；等等。

5. 可以添加一些优化，例如：将读入的词典文件进行缓存，避免每次查找变位词时都需要重新读入文件；在查找变位词时，可以先判断输入单词是否本身就是词典中的单词，避免进行不必要的计算。