请教一道hackerrank题目

lollipop3 发表于 2019-9-8 09:25
这样想，对于每一个x ,找最大的比x 大的f(x)使得 (x,f(x))区间没有冲突。
f(x) = min(f(x+1), g(x)) g(x)  ...

所以看起来是一个DP问题了？计算的话从n倒着算到1

Luffy_Tse 发表于 2019-9-8 15:04
过一遍所有的ab pair，把小id当天敌，大id当食物然后得到这个数组
int[] smallestFoodIdx
如果i不是任何 ...

如果每次只在if(i==preGroupEnd)的时候res加一，那结果应该不对吧？

DIRECTIONNZ 发表于 2019-9-9 01:19
我觉得用union find最大的问题是：比如1和7是enemy，7和5是enemy。本来1和5可以放在一起（假设1一直到6都 ...

好， 我同意你说的，这个我写到最后忘记了。

另外一个做法是这样的。

对着每一个起始点， 找第一个conflict出现的位置。

每一个起始点可能有多个conflict，或者没有。

先假定每个conflict 都在n， 或者数组外。

遍历所有的条件后， 可知每个元素的最近conflict位置。

因为是distinct element， 所以每个数字位置也distinct。

感觉你已经会做了。

DIRECTIONNZ 发表于 2019-9-9 01:24
感觉最开始确实理解错题意了。可是问题是，比如1最多到6都没有天敌，可是5和6是天敌，那么你算rst+= 6 -1 ...

没啊 你判断能不能连6的时候 要看的是6左边能连多远 能不能连到当前起点

anhpp 发表于 2019-9-9 02:21
没啊 你判断能不能连6的时候 要看的是6左边能连多远 能不能连到当前起点

ok，所以就是说：假设i在左边，j在右边，为了判断i 和j能不能连，不但要看i右边能不能连到j，还要看j往左能不能连到i。如果能连上，把j往右移1，直到发现相对于i最右边的j，算一下res += i - j + 1
是这样吧？

DIRECTIONNZ 发表于 2019-9-9 01:43
如果每次只在if(i==preGroupEnd)的时候res加一，那结果应该不对吧？

最开始就把preGroupEnd设置成第一个idx，也就是1，如果0 based 的话就0，所以在第一个动物的时候组的数量就会+1
接下来只要当前idx不等于preGroupEnd，就证明这个动物还能在继续添加到当前这个group，就没有必要+1.

DIRECTIONNZ 发表于 2019-9-9 02:32
ok，所以就是说：假设i在左边，j在右边，为了判断i 和j能不能连，不但要看i右边能不能连到j，还要看j往左 ...

意思大概是对的
预处理就是设置好 left和right 数组 都不需要排序 一直比min max就行
然后两个指针i和j j 一直右移 直到连不上i为止 i再去右移 直到能连上j, 再尝试去右移j, 每次i右移的时候 update result.