本文主要是介绍Ever Dream (ZOJ - 3700,模拟水题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一.题目链接:
ZOJ-3700
二.题目大意:
T 组数据.
n 行字符串.
现有操作:将每个单词按照出现次数分组,同组中先按长度从大到小,长度相等时,再按字典序排列.
输出规则:在出现次数 > 1 的组,输出里面最长的单词,如果最长的单词不唯一,则输出最长单词中字典序排倒数第二的字符串.
三.分析:
水题!!!
申请两个 map,一个放每个单词出现次数,另一个放出现一定次数的所有单词(优先队列呀!).
注意:".abc.",这种的要把 "abc" 分离出来(无用字符换成空格用 stringstream 分割即可),缩写算作一个单词.
应该 1A 的,5555. I am so vegetable.
四.代码实现:
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define PI acos(-1.0)
#define ll long long int
using namespace std;struct cmp
{bool operator()(string s1, string s2){if(s1.size() == s2.size())return s1 < s2;return s1.size() < s2.size();}
};bool check(char s)
{if(s >= 'a' && s <= 'z' || s == '\'' || s == ' ')return 1;return 0;
}int main()
{int T;scanf("%d", &T);while(T--){int n;scanf("%d", &n);getchar();map <string, int> cnt;map <int, priority_queue <string, vector <string>, cmp> > mp;vector <string> ans;while(n--){string str;getline(cin, str);int len = str.size();for(int i = 0; i < len; ++i){if(str[i] >= 'A' && str[i] <= 'Z')str[i] += 32;if(!check(str[i]))str[i] = ' ';}stringstream ss;ss << str;while(ss >> str)cnt[str]++;}for(map <string, int> ::iterator iter = cnt.begin(); iter != cnt.end(); ++iter)if(iter->second > 1)mp[iter->second].push(iter->first);for(map <int, priority_queue <string, vector <string>, cmp> > ::iterator iter = mp.begin(); iter != mp.end(); ++iter){priority_queue <string, vector <string>, cmp> q;q = iter->second;if(q.size() == 1)ans.push_back(q.top());else{string s1, s2;s1 = q.top();q.pop();s2 = q.top();if(s1.size() == s2.size())ans.push_back(s2);elseans.push_back(s1);}}int len = ans.size();bool flag = 0;for(int i = len - 1; i >= 0; --i){if(flag)printf(" ");cout << ans[i];flag = 1;}printf("\n");}return 0;
}
这篇关于Ever Dream (ZOJ - 3700,模拟水题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!