算法提高 P1003（排序+优先队列）

试题 算法提高 P1003

时间限制：1.0s 内存限制：256.0MB
　　作为一名网络警察，你的任务是监视电子邮件，看其中是否有一些敏感的关键词。不过，有些狡猾的犯罪嫌疑人会改变某些单词的字母顺序，以逃避检查。请编写一个程序，发现这种调整过顺序的关键词。程序的输入有两行，第一行是关键词列表，第二行是待检查的句子。程序的输出为在该句子中所找到的经过顺序调整的关键词。（单词全部为小写，单词之间以一个空格分隔，每一行的单词个数不限）

输入：
　　guns mines missiles
　　aameric ssell snug dan iimsssle ot sit neeemis

输出：
　　guns missiles

题解
??可以把每一个单词按照升序排列存储，这样如果单词是乱序的话，经过一轮sort就正序了，这时候只要查找原单词里面有没有这个单词即可。输出的时候要求按照原来的顺序输出单词，所以定义一个结构体 word ，里面记录了单词原序和经过升序排列过的的字符串。
PS. 题目没有明说，但是输出也是要按原来正序的单词的字典序输出，所以要用到优先队列。

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;struct word {
    char a[26], b[26];word(char _a[26], char _b[26]) {
    memcpy(a, _a, 26);memcpy(b, _b, 26);}
};
vector<word> myset;struct cmp {
    bool operator()(char *a, char *b) {
    if (strcmp(a, b) >= 1)return true;elsereturn false;}
};
priority_queue<char*,vector<char*>,cmp > Q;	//注意优先队列要重载运算符int main() {
    char a[26],b[26];while (scanf("%s", a)) {
    memcpy(b, a, strlen(a)+1);sort(a, a + strlen(a));myset.push_back(word(b, a));if (getchar() == '\n')break;}while (scanf("%s", a)) {
    sort(a, a + strlen(a));for (int i = 0; i < myset.size(); i++) {
    if (strcmp(a, myset[i].b) == 0) {
    Q.push(myset[i].a);}}if (getchar() == '\n')break;}while (!Q.empty()) {
    	//每次取出字典序最小的单词fputs(Q.top(),stdout);printf(" ");Q.pop();}return 0;
}