身边找不到人讨论题目...幸好还有这里
原题目：(nthu_oj)
※先声明这不是作业,只是自己的练习
http://acm.cs.nthu.edu.tw/problem.php?pid=7667
这题我的作法是把袜子宣告成一个struct来储存name,size
struct Sock{
string name,size;
}
然后定义operator <(less than operator)
再把struct(袜子)跟int(次数)存到map里
用读进来的name, size建立struct, 插入到map中
如果已经在map中,则次数递增
如果不在,则初始化为1
测试结果是正确的, 但超时...
想请问有什么方法可以做更快？
(不知道他题目中给的hint: O(nlogn)会超时的用意为何...

你的做法就是 O(nlogn)再一个提示好了: O(nlogn) 会 TLE 所以得用 O(n) 法这代表每一个输入只能用 O(1) 处理有什么方法可以让每个输入都是 O(1) 处理时间呢?注意输入资料的限制!

会变成nlogn是因为我在处理输入资料时多了一个map查查询的动作吗？阿...不好意思,问了废话...改成先把所有可能的name以及一个sizeMap放入map再读取输入时直接sockMap[name][size]++去递增次数最后traverse map一次输出.依然TLE...QQ

map操作就是logn呀,你可以想想不要用map怎么做

谢谢提示！目前用阵列四维阵列储存次数已经不会TLE

应该可以不用完整的纪录袜子数? 只要纪录有哪些袜子还没成对就好，跟目前input成对的就把他从未成对中移掉

？！楼上可以再说得更详细点吗

仔细看的话会发现袜子的种类有限

http://pastebin.com/UTiBZPV5 目前的code想请问这样再处理输入时应该是O(1)了？(直接随机存取到纪录次数的位置(ps:刚刚看到RE,以为已经没tle..

Well, 如果有两双成对的袜子输出是错的, 不过看不出来哪里RERE; 一个可能是 stdio 和 iostream 混用又没有ios_base::sync_with_stdio() 结果读错东西

Input 尚未成对(xdx X) (xdx X)(xdx X) none //以成对，故移出(xdx X) (xdx X)(xdd XL) (xdx X)(xdd XL)(xdd S) (xdx X)(xdd XL)(xdd S)(xdd M) (xdx X)(xdd XL)(xdd S)(xdd M)以第一笔测资来讲，大概是长这个样子只要记录尚未成对的袜子就可以了，最后把尚未成对的袜子按照题意做排序输出就可以了，不用记录每一种袜子出现了几支@williamd 你的code在line37的部分会出问题，@scwg说的应该就是这个问题，如果有复数双成对袜子会输出超过一次的 Socks fine.试试这个测资 http://pastebin.com/42wFL8WU

@hinet60613:阿...我误解题意(以为成对就fine...可是如果要纪录未成对的袜子,又必须在o(1)的复杂度找到尚未成对的袜子然后移出那应该用什么结构来储存比较好呢？之前我是把name的3个字母对a的offse以及size当作索引,不过,这样再输出时又需要全部遍历一次(虽然次数不算太大(26*26*26*5), 但还是跑了TLE...

bitset 擅用flip

感谢各位,刚刚发现问题了...我把output修正过后就ac了,原来,跑错的output也有可能跑到TLE QQ