作者williamd4112 (Williamd)
看板Prob_Solve
标题[问题] HappyStorm's Sock Sucks
时间Wed Jan 28 21:44:07 2015
身边找不到人讨论题目...幸好还有这里
原题目：(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)会超时的用意为何...
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.114.196.141
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1422452649.A.834.html
1F：推 LPH66: 你的做法就是 O(nlogn) 01/28 21:51
2F：→ LPH66: 再一个提示好了: O(nlogn) 会 TLE 所以得用 O(n) 法 01/28 21:52
3F：→ LPH66: 这代表每一个输入只能用 O(1) 处理 01/28 21:52
4F：→ LPH66: 有什麽方法可以让每个输入都是 O(1) 处理时间呢? 01/28 21:52
5F：→ LPH66: 注意输入资料的限制! 01/28 21:53
6F：→ williamd4112: 会变成nlogn是因为我在处理输入资料时多了一个map查 01/28 22:02
7F：→ williamd4112: 查询的动作吗？ 01/28 22:02
8F：→ williamd4112: 阿...不好意思,问了废话... 01/28 22:06
9F：→ williamd4112: 改成先把所有可能的name以及一个sizeMap放入map 01/28 22:34
10F：→ williamd4112: 再读取输入时直接sockMap[name][size]++去递增次数 01/28 22:34
11F：→ williamd4112: 最後traverse map一次输出.依然TLE...QQ 01/28 22:35
12F：→ flere: map操作就是logn呀,你可以想想不要用map怎麽做 01/28 22:39
13F：→ williamd4112: 谢谢提示！目前用阵列四维阵列储存次数已经不会TLE 01/28 23:05
14F：推 hinet60613: 应该可以不用完整的纪录袜子数? 只要纪录有哪些袜子还 01/28 23:13
15F：→ hinet60613: 没成对就好，跟目前input成对的就把他从未成对中移掉 01/28 23:14
16F：→ williamd4112: ？！楼上可以再说得更详细点吗 01/29 00:34
17F：推 guest2: 仔细看的话会发现袜子的种类有限 01/29 00:41
19F：→ williamd4112: 想请问这样再处理输入时应该是O(1)了？(直接随机存 01/29 01:19
20F：→ williamd4112: 取到纪录次数的位置(ps:刚刚看到RE,以为已经没tle.. 01/29 01:20
21F：→ scwg: Well, 如果有两双成对的袜子输出是错的, 不过看不出来哪里RE 01/29 02:22
22F：→ scwg: RE; 一个可能是 stdio 和 iostream 混用又没有 01/29 02:23
23F：→ scwg: ios_base::sync_with_stdio() 结果读错东西 01/29 02:23
24F：→ hinet60613: Input 尚未成对 01/29 15:38
25F：→ hinet60613: (xdx X) (xdx X) 01/29 15:39
26F：→ hinet60613: (xdx X) none //以成对，故移出 01/29 15:39
27F：→ hinet60613: (xdx X) (xdx X) 01/29 15:39
28F：→ hinet60613: (xdd XL) (xdx X)(xdd XL) 01/29 15:39
29F：→ hinet60613: (xdd S) (xdx X)(xdd XL)(xdd S) 01/29 15:40
30F：→ hinet60613: (xdd M) (xdx X)(xdd XL)(xdd S)(xdd M) 01/29 15:40
31F：→ hinet60613: 以第一笔测资来讲，大概是长这个样子 01/29 15:40
32F：→ hinet60613: 只要记录尚未成对的袜子就可以了，最後把尚未成对的 01/29 15:40
33F：→ hinet60613: 袜子按照题意做排序输出就可以了，不用记录每一种袜子 01/29 15:41
34F：→ hinet60613: 出现了几支 01/29 15:41
35F：→ hinet60613: @williamd 你的code在line37的部分会出问题，@scwg说 01/29 15:48
36F：→ hinet60613: 的应该就是这个问题，如果有复数双成对袜子会输出超过 01/29 15:49
37F：→ hinet60613: 一次的 Socks fine. 01/29 15:49
39F：→ williamd4112: @hinet60613:阿...我误解题意(以为成对就fine... 01/29 16:42
40F：→ williamd4112: 可是如果要纪录未成对的袜子,又必须在o(1)的复杂度 01/29 16:44
41F：→ williamd4112: 找到尚未成对的袜子然後移出 01/29 16:45
42F：→ williamd4112: 那应该用什麽结构来储存比较好呢？ 01/29 16:45
43F：→ williamd4112: 之前我是把name的3个字母对a的offse以及size当作索 01/29 16:47
44F：→ williamd4112: 引,不过,这样再输出时又需要全部遍历一次(虽然次数 01/29 16:48
45F：→ williamd4112: 不算太大(26*26*26*5), 但还是跑了TLE... 01/29 16:48
46F：推 EdisonX: bitset 擅用flip 01/29 20:01
47F：→ williamd4112: 感谢各位,刚刚发现问题了...我把output修正过後就ac 01/30 01:21
48F：→ williamd4112: 了,原来,跑错的output也有可能跑到TLE QQ 01/30 01:22