360笔试第二题 高效+简单的解法

#include <vector>
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
bool cmp(int a, int b)
{
	return a > b;
}
void swap(int& a, int& b)
{
	int c = a;
	a = b;
	b = c;
}
int main()
{
	int n, m;
	while (cin >> n >> m)
	{
		ifstream in("C:\\Users\\ASUS\\Desktop\\1.txt");
		in >> n >> m;
		int *number1 = new int[n];
		int *number2 = new int[n];
		int *result = new int[m];
		vector<bool> flag(n, false);
		memset(result, 0, sizeof(int)*m);
		for (int i = 0;i < n;++i)
		{
			//int temp;
			//cin >> temp;
			//number1[i] = temp;
			in >> number1[i];
		}
		for (int i = 0;i < n;++i)
		{
			//int temp;
			//cin >> temp;
			//number2[i] = temp;
			in >> number2[i];
		}
		sort(number1, number1 + n, cmp);
		sort(number2, number2 + n,cmp);
		int start = 0;
		int end = n - 1;
		for (int i = 0;i < n;++i)//循环n次
		{
			bool valid = false;
			int pos = lower_bound(number2, number2 +n,m-1-number1[i],cmp) - number2;
			int numOne = (number1[i] + number2[start]) % m;
			int numTwo = (number1[i] + number2[end]) % m;
			int numThr = INT_MIN;
			if(pos<end&&pos>start&&flag[pos])//二分查找 logN
			{
				while (1)
				{
					int tt;
					while (flag[pos])
					{
						tt = pos;
						pos = (pos + start) / 2;
					}
					if (flag[pos + 1])
						break;
					while (!flag[pos])
					{
						if (pos == tt - 1)break;
						pos = (pos + tt) / 2;
					}
				}
			}
			if (pos >= end || pos <= start)
				valid = true;
			else
			numThr = (number1[i] + number2[pos]) % m;
			if (!flag[end]&&numOne <= numTwo&&(valid||(numTwo>=numThr)))
			{
				int apos = lower_bound(number1+i, number1 + n, m - 1 - number2[end], cmp) - number1;
				if(apos==n)
				{ }
				else
				{
					int temp = (number2[end] + number1[apos]) % m;
					if (temp > numTwo)
					{
						swap(number1[i], number1[apos]);
						numTwo = temp;
					}
					sort(number1 + i + 1, number1 + n, cmp);//NlogN 快排，少数情况下进来
				}
				flag[end] = true;
				--end;
				result[numTwo]++;
				while (end - 1 >= 0&&end>=0&&flag[end])
					--end;
			}
			else if(!flag[start]&&numOne> numTwo&&(valid||(numOne>=numThr)))
			{

				int apos = lower_bound(number1 + i, number1 + n, m - 1 - number2[start], cmp) - number1;
				if (apos == n)
				{
				}
				else
				{
					int temp = (number2[start] + number1[apos]) % m;
					if (temp > numOne)
					{
						swap(number1[i], number1[apos]);
						numOne = temp;
					}
					sort(number1 + i + 1, number1 + n, cmp);//NlogN 快排，少数情况下进来
				}

				flag[start] = true;
				++start;
				result[numOne]++;
				while (flag[start]&&start+1<=n-1&&start<n)
					++start;
			}
			else if(pos<n)
			{
				int apos = lower_bound(number1 + i, number1 + n, m - 1 - number2[pos], cmp) - number1;
				if (apos == n)
				{
				}
				else
				{
					int temp = (number2[pos] + number1[apos]) % m;
					if (temp > numThr)
					{
						swap(number1[i], number1[apos]);
						numThr = temp;
					}
					sort(number1 + i + 1, number1 + n, cmp);//NlogN 快排，少数情况下进来
				}
				flag[pos] = true;
				result[numThr]++;
			}
		}
		for (int i = m - 1;i >= 0;--i)
		{
			while (result[i] != 0)
			{
				cout << i << " ";
				--result[i];
			}		
		}
		cout << endl;
	}
}