【差分数组】【图论】【分类讨论】【整除以2】100213按距离统计房屋对数目

本文介绍: 给你三个正整数 n 、x 和 y 。在城市中，存在编号从 1 到 n 的房屋，由 n 条街道相连。对所有 1

⎧i−x+j−yi−x+y−jx−i+j−yx−i+y−ji>=x,j>=yx>=i,j<yi<x,j>=yi<x,j<y一三四六

我们枚举i，计算j，故x,y,i可以看做常数，可以求出相等的临界值的j。
情况二一：
i-x + j- y <= j – i -1

→

rightarrow

$\to$ 2i -x – y <= -1

→

rightarrow

$\to$ 2i <= x+y-1

→

rightarrow

$\to$

{

→

∗

−

→

begin{cases} i rightarrow x rightarrow y rightarrow j & 2*i <= x+y-1\ i rightarrow j & else end{cases}

${i \to x \to y \to j i \to j 2 * i <= x + y - 1 e l se$
和j无关

情况二三：
i-x +y-j <= j – i -1

→

rightarrow

$\to$ 2*(i-j) -x + y <= -1

→

rightarrow

$\to$ -2j <= x – y – 2i -1注意除以-1，大于会变小于。

→

rightarrow

$\to$ 2j >= y-x+2i+1

→

rightarrow

$\to$ j >= (y-x)/2 + i +1

{

→

(

−

)

→

begin{cases} i rightarrow x rightarrow y rightarrow j & j >= (y-x)/2 + i +1 \ i rightarrow j & else end{cases}

${i \to x \to y \to j i \to j j >= (y - x) /2 + i + 1 e l se$
情况二四：
要想通过x,y 必须 x-i + j- y <= j – i -1

→

rightarrow

$\to$ x-y <= -1

→

rightarrow

$\to$ x <y，恒成立。

情况二六：
要想通过x,y，必须 x-i+y-j <= j – i -1

→

rightarrow

$\to$ x+y-2j <= -1

→

rightarrow

$\to$ -2j <= -x-y-1 注意除以-1，大于会变小于。

→

rightarrow

$\to$ 2j >= x+y+1

→

rightarrow

$\to$ j>=(x+y+1+1)/2

{

→

(

)

→

begin{cases} i rightarrow x rightarrow y rightarrow & j>=(x+y+1+1)/2 \ i rightarrow j & else end{cases}

${i \to x \to y \to i \to j j >= (x + y + 1 + 1) /2 e l se$

y >= 0 整除2的逆运算

2x >= y ，如果y是偶数等效与 x >= y/2 。如果y是奇数，等效与 x >= (y+1)/2 。两者可以统一为: x >=(y+1)/2 。
2x > y 如果y是偶数等效与 x > y/2 。如果y是奇数，等效与 x > y/2。两者统一为x > y/2。
2x <= y 可以统一为 x <=y/2。
2x < y 可以统一为：x < ( y+1)/2

代码

核心代码

class Solution {
public:
	vector<long long> countOfPairs(int n, int x, int y) {		
		vector<long long> vRet(n);
		if (x == y)
		{
			vRet.clear();
			for (int i = n - 1; i >= 0; i--)
			{
				vRet.emplace_back(i * 2);
			}
			return vRet;
		}
		if (x > y )
		{
			swap(x, y);
		}
		x--;
		y--;
		int i = 0;
#define Path1(j) (j - i -1 )
		auto Path2 = [&i,&x,&y]( const int j)
		{
			return abs(i - x) + abs(j - y);
		};
		vector<long long> vDiff(n);
		auto Add = [&](int left, int len)
		{
			if (len <= 0)
			{
				return;
			}
			vDiff[left] += 2 ;
			vDiff[left+len] -= 2 ;
		};
		
		for (; i < x; i++)
		{
			//j 在[y,n)
			const int iy = max(i + 1, y);
			if (n - iy > 0)
			{
				Add(Path2(iy), n - iy);
			}	
			//j在(i,y)
			if( y - i -1 > 0 )
			{//i->x->y-j [j0,y)
				const int j0 = (x + y + 2) / 2;	
				Add(Path2(y-1), y - j0);
				//(i,j0)
				Add(0, j0 - i - 1);
			}
		}
		for (; i < n; i++)
		{
			//j在(max(y-1,i),n)
			if (2*i <= x + y-1)
			{//i->x->y-j
				Add(Path2(max(y-1, i) +1), n - max(y-1, i) -1);
			}
			else
			{
				Add(Path1(max(y-1, i) +1), n - max(y-1, i) -1);
			}
			//j在(i,y)
			if (y - i - 1 > 0)
			{
				int j0 = min(y,(2 * i + y - x + 2) / 2);
				j0 = max(j0, i + 1);
				//if (y - j0 >= 0)
				{
					//j在[j0,y) i->x->y-j 
					Add(Path2(y - 1), y - j0);
					//j在(i,j0)
					Add(0, j0 - i - 1);
				}
			}
		}
		
		long long cur=0;
		for (int i = 0; i < n; i++)
		{
			cur += vDiff[i];
			vRet[i] = cur;
		}
		return vRet;
	}
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{	
	int n,  x,  y;

	{
		Solution sln;
		n = 6, x = 1, y = 5;
		auto res = sln.countOfPairs(n, x, y);
		Assert(res, vector<long long>{ 12, 14, 4, 0, 0, 0 });
	}

	{
		Solution sln;
		n = 3, x = 2, y = 2;
		auto res = sln.countOfPairs(n, x, y);
		Assert(res, vector<long long>{4, 2, 0});
	}

	{
		Solution sln;
		n = 4, x = 1, y = 1;
		auto res = sln.countOfPairs(n, x, y);
		Assert(res, vector<long long>{6, 4, 2, 0});
	}
	{
		Solution sln;
		n = 5, x = 2, y = 4;
		auto res = sln.countOfPairs(n, x, y);
		Assert(res, vector<long long>{10, 8, 2, 0, 0});
	}
	
	
	{
		Solution sln;
		n = 3, x = 1, y = 3;		
		auto res = sln.countOfPairs(n,x,y);
		Assert(res, vector<long long>{6, 0, 0});
	}		
	
	{
		Solution sln;
		n = 2, x = 2, y = 2;
		auto res = sln.countOfPairs(n, x, y);
		Assert(res, vector<long long>{2, 0});
	}
	
	

	
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛