请教一道hackerrank题目

如图所示，请教一道hackerrank上面的题目。之前考虑并查集，但是发现enemy并没有传递性，比如1和3是enemy， 2和3是enemy，但1和2并不是enemy，那么放在一个union里面是不对的。
考虑到题目给的数据规模不小，感觉n^2的时间复杂度估计会TLE。想请教各位大佬，有没有好一点的解法。
谢谢大家～有好的答案一定会加米。

显然union find。。

这题你得先明白最笨的方法怎么做。。
一句话总结的话就是对于每一个起始点， 找有多少个subarray不包含conflict

伪代码即
for i = 0 to n - 1
  for j = i to n - 1
    if(no_conflict(i, j)) then re++
return re

这里 no_conflict(i, j)的意思是从i到j之间没有conflict， 也就是根据你m条内容做出来的。

那么显然这是一个n方 * O(no_conflict()) 的解法。

如何优化？

注意：
1） 一旦有conflict， 即停止。
2） 如果[i, j] 间无conflict，即 [i + 1, j]间无conflict
3）no_conflict 可以用union find优化。
即， 把j的这段循环改成一个尺取法即可。

改代码为
j = 0
for i = 0 to n - 1
  while j < n && no_conflict(i, j) j++
  re += j - i
return re

这里no_conflict你需要考虑一下。。 基本上就是union find的一个应用， 试一下

过一遍所有的ab pair，把小id当天敌，大id当食物然后得到这个数组
int[] smallestFoodIdx
如果i不是任何的天敌，那么smallestFoodIdx = Integer.MAX_VALUE
然后就一个个group来，算最远距离
int preGroupEnd = 1;
int res = 0;
for(int idx = 1; i<=n; ++i){
  if(i==preGroupEnd){
    ++res;
    preGroupEnd = smallestFoodIdx[i][i];
  }else{
    preGroupEnd = Math.min(preGroupEnd, smallestFoodIdx[i])[i];
  }
}

算法复杂度是O(n+m)：需要过一遍所有的边，然后还要过一遍所有点。
[/i][/i][/i][/i]

since the animals can't not be reordered and skipped. just arrange the animal from beginning.  O(n) Solution. Not quite understand the ouput, how many possible ways or just any of the working methods with total group numbers?

randallhong 发表于 2019-9-8 08:02
since the animals can't not be reordered and skipped. just arrange the animal from beginning.  O(n)  ...

how many possible ways

DIRECTIONNZ 发表于 2019-9-8 08:03
how many possible ways

find the longest possible length in each group.  for example in you case, it will be 2, 1.
then total possible ways will be 2^1 * 2^0 = 2
if the length is 3,3,3, then the total possible ways = 2^2 * 2^2 *2^2 = 64.

errr 貌似你们题意理解错了
应该大概先给m个pair 排个序 预处理一下
然后找出 对于任意一个i 左右分别最多能连到多远

然后从头到尾扫过去
比如现在发现 2开头 最远右边可以连到6，cnt += (6-2+1)
然后3开头 挨个判断7，8，9能不能连(用预处理的信息，7左边能不能连到3)

这样想，对于每一个x ,找最大的比x 大的f(x)使得 (x,f(x))区间没有冲突。
f(x) = min(f(x+1), g(x)) g(x) 就是比x 大的且与x有冲突的最小index。
然后所有的区间数就是 sum (f(x) - x + 1)

337845818 发表于 2019-9-9 01:06
显然union find。。

这题你得先明白最笨的方法怎么做。。

我觉得用union find最大的问题是：比如1和7是enemy，7和5是enemy。本来1和5可以放在一起（假设1一直到6都没有conflict），可是用了union find的结果是，这个interval从1出发最多到4，因为到5这里已经断了。所以因为这种conflict不具有传递性，而union find是可以让conflict传递的

anhpp 发表于 2019-9-8 09:14
errr 貌似你们题意理解错了
应该大概先给m个pair 排个序 预处理一下
然后找出 对于任意一个i 左右分别最 ...

感觉最开始确实理解错题意了。可是问题是，比如1最多到6都没有天敌，可是5和6是天敌，那么你算rst+= 6 -1 +1的时候不是把5也算进去了吗？