CodeForces 1506F Triangular Paths 找规律 路径

CodeForces 1506F Triangular Paths 找规律 路径

【题目描述】
Consider an infinite triangle made up of layers. Let’s number the layers, starting from one, from the top of the triangle (from top to bottom). The k-th layer of the triangle contains k points, numbered from left to right. Each point of an infinite triangle is described by a pair of numbers (r,c) (1≤c≤r), where r is the number of the layer, and c is the number of the point in the layer. From each point (r,c) there are two directed edges to the points (r+1,c) and (r+1,c+1), but only one of the edges is activated. If r+c is even, then the edge to the point (r+1,c) is activated, otherwise the edge to the point (r+1,c+1) is activated. Look at the picture for a better understanding.

Activated edges are colored in black. Non-activated edges are colored in gray.
From the point (r1,c1) it is possible to reach the point (r2,c2), if there is a path between them only from activated edges. For example, in the picture above, there is a path from (1,1) to (3,2), but there is no path from (2,1) to (1,1).

Initially, you are at the point (1,1). For each turn, you can:

Replace activated edge for point (r,c). That is if the edge to the point (r+1,c) is activated, then instead of it, the edge to the point (r+1,c+1) becomes activated, otherwise if the edge to the point (r+1,c+1), then instead if it, the edge to the point (r+1,c) becomes activated. This action increases the cost of the path by 1;
Move from the current point to another by following the activated edge. This action does not increase the cost of the path.
You are given a sequence of n points of an infinite triangle (r1,c1),(r2,c2),…,(rn,cn). Find the minimum cost path from (1,1), passing through all n points in arbitrary order.

【输入】
The first line contains one integer t (1≤t≤104) is the number of test cases. Then t test cases follow.

Each test case begins with a line containing one integer n (1≤n≤2⋅105) is the number of points to visit.

The second line contains n numbers r1,r2,…,rn (1≤ri≤109), where ri is the number of the layer in which i-th point is located.

The third line contains n numbers c1,c2,…,cn (1≤ci≤ri), where ci is the number of the i-th point in the ri layer.

It is guaranteed that all n points are distinct.

It is guaranteed that there is always at least one way to traverse all n points.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.

【输出】
For each test case, output the minimum cost of a path passing through all points in the corresponding test case.

【样例输入】

4
3
1 4 2
1 3 1
2
2 4
2 3
2
1 1000000000
1 1000000000
4
3 10 5 8
2 5 2 4

【样例输出】

0
1
999999999
2

【解题思路】
题目给出一个无限大的三角形图，对于图中的每个结点，有一条有向边指向它下一行的一个结点，初始方向与结点的行列坐标有关，当行列坐标和为偶数时指向左下方结点，为奇数时指向右下方结点。
答案要求的是从(1,1)点出发，走过输入给出的每个结点，至少要改变多少条边的方向。
我们进行分析发现，点和边之间是存在规律的。从左上往右下方向的每条斜线上，第奇数条线上没有任何有向边，且线上每个点的行列坐标之和为偶数，在这条线上每走一步都要改变一条边的方向；第偶数条线所有点之间都有有向边，且线上每个点的行列坐标之和为奇数，在这条边上走任何步数都无需改变任何边的方向。
因为边是有向的，显然我们只可能从上往下走。因此我们对输入的点进行排序，行数小的在前面。
我们从点(1,1)开始往下考虑，前一个点的行列坐标之差用t1记录，行列坐标之和用x1记录；后一个点的行列坐标之差用t2记录，行列坐标之和用x2记录。我们按照找到的规律，分类讨论即可，代码当中作了具体的注释。

【AC代码】

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node
{
   
	int r,c;
}a[200005];
bool cmp(node a,node b)
{
   
	return a.r<b.r;
}
int main()
{
   
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T,n;
	cin>>T;
	while(T--)
	{
   
		cin>>n;
		for(int i=0;i<n;i++)
			cin>>a[i].r;
		for(int i=0;i<n;i++)
			cin>>a[i].c;
		sort(a,a+n,cmp);
		int ans=0,t1=0,x1=2;//从(1,1)点开始走，t为斜线编号，x为点的行列数之和 
		for(int i=0;i<n;i++)
		{
   
			int t2=a[i].r-a[i].c,x2=a[i].r+a[i].c;
			if(t1==t2&&x1%2==1||t2-t1==1&&x1%2==0)//在同一条1线上或相邻01线上 
				continue;
			else if(t1==t2&&x1%2==0)//在同一条0线上 
				ans+=(x2-x1)/2;
			else
			{
   
				if(x1%2==0) t1++;//如果前一个点在0线上，先往左下走，无需步数 
				ans+=(t2-t1+1)/2;
			}
			t1=t2;x1=x2;//继续 
		}
		cout<<ans<<endl;
	}
	return 0;
}