Zhangwen
BAN USERAnother idea is to first sort the array and its position, then compare the relative position change in the sorted array and position data from small to big value
struct Point{
int val,pos;
}point[N];
for(i=0;i<n;i++){
point[i].val = array[i];
point[i].pos = i;
}
sort(point,point+n,cmp);
int ans = 0;
int pos[N];
for(i=0;i<n;i++){
x = point[i].pos
while(x < i){point[i].pos = pos[x];x=pos[x];}
ans += point[i].pos-i;
pos[i] = point[i].pos
}
Illustration:
[3,2,4,1]
=> [(3,0),(2,1),(4,2),(1,3)]
sort: [(1,3),(2,1),(3,0),(4,2)]
Check (1,3), as it is smallest, when it move from previous position to current, the unordered pair has reduced pre.pos-cur.pos, that is 3-0=3
After doing this, we update the left as
[(1,3)(2,1),(3,0),(4,2)]
Since unordered pairs has been calculated for (1,3), we would not include this in the following calculation, so we have to update the one whose position is 0 to element 0 's original position. So (3,0) should be updated to (3,3) since element 0's original position is 3
The new array would be sorted from pos 1 and the postion value would also be ranged from 1 to n-1
So we do similar actions as before
[(1,3)(2,1),(3,3),(4,2)]
Based on wws's comment, we can simulate the whole process:
For every maximum connected subgraph:
We random select a point and assign its position (0,0)
For every new point that is connected to this point, calculate their positions.
Select the new point, and for every point that is connected to this, if the point has position, check whether it is right, otherwise, calculate it and keep it.
Do this process until all the edges has been checked.
Example:
p0 W p1, p1 SW p2, p2 SE p3, p3 NE p0,p6 W p7
We can easily judge that (p0,p1,p2,p3) and (p6,p7) are maximum connected subgraph.
For (p0,p1,p2,p3):
We assign p0 (0,0)
p0 W p1 => p1 (1,0)
p1 SW p2 => p2 (2,1)
p2 SE p3 => p3(1,2)
p3 NE p0 => we know p0, so check whether p3 NE p0 => False
Of course sometimes when we select p0 and assign the coordinator, but edges connected to p0 would be mentioned later. So we'd better store all the connected points for every point.
- Zhangwen November 04, 2014