微软2014见习生及秋令营技术类职位在线测试第3题

微软2014实习生及秋令营技术类职位在线测试第3题

昨天，有很多同学参加微软2014实习生及秋令营技术类职位在线测试，有些还拿了350分，实在是厉害。

第三题是这样的

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

Description

Find a pair in an integer array that swapping them would maximally decrease the inversion count of the array. If such a pair exists, return the new inversion count; otherwise returns the original inversion count.

Definition of Inversion: Let (A[0], A[1] ... A[n]) be a sequence of n numbers. If i < j and A[i] > A[j], then the pair (i, j) is called inversion of A.

Example:
Count(Inversion({3, 1, 2})) = Count({3, 1}, {3, 2}) = 2
InversionCountOfSwap({3, 1, 2})=>
{
InversionCount({1, 3, 2}) = 1 <-- swapping 1 with 3, decreases inversion count by 1
InversionCount({2, 1, 3}) = 1 <-- swapping 2 with 3, decreases inversion count by 1
InversionCount({3, 2, 1}) = 3 <-- swapping 1 with 2 , increases inversion count by 1
}

Input

Input consists of multiple cases, one case per line.Each case consists of a sequence of integers separated by comma.

Output

For each case, print exactly one line with the new inversion count or the original inversion count if it cannot be reduced.

样例输入

3,1,2
1,2,3,4,5

样例输出

1
0

就是给我们一个数组，让我们只交换其中的两个元素一次，使得逆序数降低的最多。

最普通的方法，无非是遍历O(n^2)，然后每次计算逆序数，复杂度是O(n^4)

稍微改进一下，计算逆序数利用分治法，修改mergesort,复杂度也还是O(n^3*logn)

再稍微改进一下，当我们交换a[i]和a[j]时，对i前面和j后面的逆序数不产生影响，只对i,j中间的产生影响

今天，我又尝试了一下贪心算法，就是交换改变距离最大的，那么什么是距离最大呢？

比如我有数组5,3,1,2,4

排序完的话是1,2,3,4,5

5，3的距离是0，这是因为5换到3后，距离排序完的5近了一步，但是3换过去距离排序完的3又远了。

5，1的距离是4，交换后都近了2格

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <time.h>

using namespace std;

int abs(int a,int b)
{
	if(a > b)
		return b-a;
	return a-b;
}

int count1(vector<int>& array, int len)
{
	int r = 0;
	for(int i = 0;i < len;i++){
		for(int j = i+1;j< len;j++){
			if(array[i] > array[j])
				r++;
		}
	}
	return r;
}

int count2(vector<int>& array, int len)
{
	vector<int>dup = array;
	sort(dup.begin(),dup.end());
	map<int,int>index;
	for(int i = 0;i<len;i++)
		index[dup[i]] = i;
	
	
	int r1 = 0,r2 = 0,diff = -1;	
	for(int i = 0;i < len;i++)
	{
		for(int j = i+1; j < len;j++)
		{
			if(array[i] > array[j])
			{
				int index1 = index[array[i]];
				int index2 = index[array[j]];
				int differ1 = abs(index1 - i) - abs(index1 - j);
				int differ2 = abs(index2 - j) - abs(index2 - i);
				if((differ1+differ2) > diff)
				{
					diff = differ1+differ2;
					r1 = i;
					r2 = j;
				}
			}
		}
	}

	int tmp = array[r1];
	array[r1] = array[r2];
	array[r2] = tmp;
	int count = count1(array,len);
	return count;
}

// random generator function:
int myrandom (int i) { return std::rand()%i;}

int main(int argv, char** args)
{
	srand(time(NULL));
	vector<int>arr;
	int len = 100;
	for(int i = 1;i <= len; i++)
		arr.push_back(i);
		
		
	while(1){	
		random_shuffle(arr.begin(), arr.end(), myrandom);

		//计算min_count
  		int min_count = count1(arr, len);
		for(int i = 0;i < len;i++){
			for(int j = i+1;j < len;j++){
				if(arr[i] >  arr[j]){
					int tmp = arr[i];
					arr[i] = arr[j];
					arr[j] = tmp;
					int count = count1(arr,len);
					if(min_count > count)
						min_count = count;
					tmp = arr[i];
					arr[i] = arr[j];
					arr[j] = tmp;
				}
			}
		}
		cout << min_count << endl;
	
		//第二种方法
		int min_count_2 = count2(arr, len);
		cout << min_count_2 <<endl;
		
		if(min_count !=  min_count_2)break;
	}
  	return 0;
}

这是最原始的方法和贪心算法在一起，当我令数组大小为100，下面是我的输出

2592

2210

2517

2717

2296

2370

2283

2423

2254

2402

2408

看来这种贪心算法也是只能找到比较优的解而无法找到最优的解

实在是想不出什么好解法了，如果你知道，一定要告诉我！！

微软2014见习生及秋令营技术类职位在线测试第3题

Description

Input

Output

相关推荐