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

作者推荐

【动态规划】【数学】【C++算法】18赛车

本文涉及知识点

差分数组 图论 分类讨论 整除以2

LeetCode3017按距离统计房屋对数目

给你三个 正整数 n 、x 和 y 。

在城市中，存在编号从 1 到 n 的房屋，由 n 条街道相连。对所有 1 <= i < n ，都存在一条街道连接编号为 i 的房屋与编号为 i + 1 的房屋。另存在一条街道连接编号为 x 的房屋与编号为 y 的房屋。

对于每个 k（1 <= k <= n），你需要找出所有满足要求的 房屋对 [house1, house2] ，即从 house1 到 house2 需要经过的 最少 街道数为 k 。

返回一个下标从 1 开始且长度为 n 的数组 result ，其中 result[k] 表示所有满足要求的房屋对的数量，即从一个房屋到另一个房屋需要经过的 最少 街道数为 k 。

注意，x 与 y 可以 相等 。

示例 1：

输入：n = 3, x = 1, y = 3

输出：[6,0,0]

解释：让我们检视每个房屋对

• 对于房屋对 (1, 2)，可以直接从房屋 1 到房屋 2。
• 对于房屋对 (2, 1)，可以直接从房屋 2 到房屋 1。
• 对于房屋对 (1, 3)，可以直接从房屋 1 到房屋 3。
• 对于房屋对 (3, 1)，可以直接从房屋 3 到房屋 1。
• 对于房屋对 (2, 3)，可以直接从房屋 2 到房屋 3。
• 对于房屋对 (3, 2)，可以直接从房屋 3 到房屋 2。
  示例 2：
  输入：n = 5, x = 2, y = 4
  输出：[10,8,2,0,0]
  解释：对于每个距离 k ，满足要求的房屋对如下：
• 对于 k == 1，满足要求的房屋对有 (1, 2), (2, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3), (4, 5), 以及 (5, 4)。
• 对于 k == 2，满足要求的房屋对有 (1, 3), (3, 1), (1, 4), (4, 1), (2, 5), (5, 2), (3, 5), 以及 (5, 3)。
• 对于 k == 3，满足要求的房屋对有 (1, 5)，以及 (5, 1) 。
• 对于 k == 4 和 k == 5，不存在满足要求的房屋对。
  示例 3：
  输入：n = 4, x = 1, y = 1
  输出：[6,4,2,0]
  解释：对于每个距离 k ，满足要求的房屋对如下：
• 对于 k == 1，满足要求的房屋对有 (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), 以及 (4, 3)。
• 对于 k == 2，满足要求的房屋对有 (1, 3), (3, 1), (2, 4), 以及 (4, 2)。
• 对于 k == 3，满足要求的房屋对有 (1, 4), 以及 (4, 1)。
• 对于 k == 4，不存在满足要求的房屋对。

分类讨论

x,y从1开始，x–,y–让其从0开始。如果x> y，交换x和y。

如果xy，直接处理：{(n-1)*2,(n-2)2…}
题目要计算的是：除了起点和终点外，经过的房屋数。
起点i和终点j相同，不统计。
起点和终点互换，需要统计。可以只统计起点<终点，最后将结果2。
整个路径可以四个节点i,x,y,j表示。
一，各节点最多出现1次，否则有环，将环删除。
二，i,j 必定出现1次，x和y要么都出现1次，要么不出现。
三，第一个节点必定是i,最后一个节点必定是j。
理论上有六种可能，实际上只有五种：
一，i → \rightarrow→ j。
二，i → \rightarrow→ x → \rightarrow→ y → \rightarrow→ j。
三，i → \rightarrow→ y → \rightarrow→ x → \rightarrow→ j。这中可能不存在：
{ 到 y 之前已经到达终点 , j < = y y → x → y 这段路程是多走的 j > y \begin{cases} 到y之前已经到达终点, & j <= y \\ y \rightarrow x \rightarrow y这段路程是多走的 & j > y \\ \end{cases}{到y之前已经到达终点,y→x→y这段路程是多走的j<=yj>y
四, x == i,y == i 结果是0。 x → \rightarrow→ y
五，xi,y不等于j。 x → \rightarrow→ y → \rightarrow→ j

六，x!=i,y等于j。 i → \rightarrow→ x → \rightarrow→ y

第一种可能经过的房屋数（不包括起点终点）：j-i-1

第二种情况，x==y，无需做特殊处理，会被淘汰。x < y时。

abs(x-i)+ abs(j-y) → \rightarrow→ abs(x-i)+abx(j-y)

{ i − x + j − y i > x , j > y 一 i − x i > x , j = = y 二 i − x + y − j x > i , j < y 三 x − i + j − y i < x , j > y 四 x − i i < x , j = = y 五 x − i + y − j i < x , j < y 六 j − y i = = x , j > y 七 0 i = = x , j = = y 八 y − j i = = x , j < y 九 \begin{cases} i-x + j- y & i > x ,j>y &一\\ i-x & i > x, j == y &二\\ i-x +y-j & x > i ,j < y &三\\ x-i + j- y & i < x,j > y &四\\ x-i & i < x,j == y & 五\\ x-i+y-j & i < x,j < y& 六\\ j - y & i == x ,j > y &七 \\ 0 & i== x ,j == y & 八\\ y - j & i==x,j < y & 九 \\ \end{cases}⎩⎨⎧i−x+j−yi−xi−x+y−jx−i+j−yx−ix−i+y−jj−y0y−ji>x,j>yi>x,j==yx>i,j<yi<x,j>yi<x,j==yi<x,j<yi==x,j>yi==x,j==yi==x,j<y一二三四五六七八九

一，二，七，八 可以合并，合并后 i >=x j >= y 。 四五可以合并，i < x ,j >=y 三九也可以合并。合并i >=x ,j<y

{ i − x + j − y i > = x , j > = y 一 i − x + y − j x > = i , j < y 三 x − i + j − y i < x , j > = y 四 x − i + y − j i < x , j < y 六 \begin{cases} i-x + j- y & i >= x ,j>=y &一\\ i-x +y-j & x >= i ,j < y &三\\ x-i + j- y & i < x, j >= y &四\\ x-i+y-j & i < x,j < y& 六\\ \end{cases}⎩⎨⎧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→ 2i -x - y <= -1 → \rightarrow→ 2i <= x+y-1 → \rightarrow→

{ i → x → y → j 2 ∗ i < = x + y − 1 i → j e l s e \begin{cases} i \rightarrow x \rightarrow y \rightarrow j & 2*i <= x+y-1\\ i \rightarrow j & else \end{cases}{i→x→y→ji→j2∗i<=x+y−1else

和j无关

情况二三：

i-x +y-j <= j - i -1 → \rightarrow→ 2*(i-j) -x + y <= -1 → \rightarrow→ -2j <= x - y - 2i -1注意除以-1，大于会变小于。→ \rightarrow→ 2j >= y-x+2i+1 → \rightarrow→ j >= (y-x)/2 + i +1

{ i → x → y → j j > = ( y − x ) / 2 + i + 1 i → j e l s e \begin{cases} i \rightarrow x \rightarrow y \rightarrow j & j >= (y-x)/2 + i +1 \\ i \rightarrow j & else \end{cases}{i→x→y→ji→jj>=(y−x)/2+i+1else

情况二四：

要想通过x,y 必须 x-i + j- y <= j - i -1 → \rightarrow→ x-y <= -1 → \rightarrow→ x <y，恒成立。

情况二六：

要想通过x,y，必须 x-i+y-j <= j - i -1 → \rightarrow→ x+y-2j <= -1 → \rightarrow→ -2j <= -x-y-1 注意除以-1，大于会变小于。 → \rightarrow→ 2j >= x+y+1 → \rightarrow→ j>=(x+y+1+1)/2

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

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});
  }
  
  
  
}