orz。如此一个水题让我想了很久用了无数STL之后已然WA到死。直到想明白自己哪里错了。
哎，自己的贪心果断不靠谱啊。但是为啥他们那些如此暴力的做法都能过呢- -构造卡N^3的数据太难了是么。。
题目大意：
n(int,[1,1000]), d(int,[1,1000])
n条记录，每条记录有a,b(string,len[1,20]),t(int,[0,10000])。按非降序列给出。
a,b,t表示在t时刻，a给b发了一条信息。
约束条件，如果a给b在t1时刻发了信息，且b给a在t2时刻发了信息，且0 < t2 - t1 <= d。那么a和b就是朋友关系。
(不存在自己给自己发消息的情况）
让你给出朋友关系的条数，和每条朋友关系，spj。
我的做法：
错误做法，N*logN的贪心：
逐条读入，用string存unique的string，map存映射。用int[][]存发送时间，abt则rel[index(a)][index(b)] = max(t, rel[index(a)][index(b)]。并与rel[index(b)][index(a)]比较，如果满足约束条件则将(a,b)插入一个set中。
错误关键点：在线更新rel[][]是不对的，虽说两个人的朋友关系与否只和最近一次的两人互通消息有关，但是这中间存在一个反例（由于题目条件的特殊性）：
a b 1
a b 2
b a 2
这组例子a、b是朋友关系。但是由于rel[index(a)][index(b)] = 2 其矩阵对称值也为2，所以不满足约束关系，所以就判错了。
所以一个简单的正确做法为离线做。
正确做法，N^2*logN的枚举：
对于每条记录枚举之前所有记录，看满足约束条件否，满足则扔set。。
（ps，有人用vector代替set都不超时。。。N^3啊，泪目）
（贪心什么的，一证明，二想反例，一定要慎重啊。自己还是太弱了。
太伤了。。。