F. Triangular Paths - Codeforces Round #710 (Div. 3)

https://codeforces.com/contest/1506/problem/F

题目描述 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.!

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≤10⁴) 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⋅10⁵) is the number of points to visit. The second line contains n numbers r₁,r₂,…,r_n (1≤r_i≤10⁹), where r_i is the number of the layer in which i-th point is located.
The third line contains n numbers c₁,c₂,…,c_n (1≤c_i≤r_i), where c_i is the number of the i-th point in the r_i 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⋅10⁵.

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

思路：
容易观察到，如果当前的r+c为奇数，那么这个路径将会一直向(r+1,c+1)方向延伸（始终有r+c为奇数），此时如果我们花费1，就可以让之后两条路径的方向变为(r+1,c)，然后再恢复(r+1,c+1)的方向。

最初在点(1,1)，然后把所有目标点按照层次从小到大先排序（题目保证了同一层不可能出现两个点）。
放在下面的代码里，就是nowr=nowc=1，然后开始按照目标点依次模拟。

如果下一个目标点在nowr的下一层，那么按题意写即可（这个要特别做）；
如果下一个目标点在nowr的下面很多（>1）层，那么就要看这样一条路径里面需要多少个(r+1,c)方向，并根据结果计算花费即可。因为我们知道，(r+1,c+1)方向其实是免费的，不需要考虑。
考虑的时候，要综合判断 nowr+nowc 是奇数还是偶数，因为这将决定你是否拥有1个免费的(r+1,c)方向路径。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
template<class _T>inline void read(_T &_a)
{
    bool f=0; char _c=getchar(); _a=0;
    while(_c<'0'||_c>'9'){ if(_c=='-') f=1; _c=getchar(); }
    while(_c>='0'&&_c<='9'){ _a=(_a<<3)+(_a<<1)-'0'+_c; _c=getchar(); }
    if(f) _a=-_a;
}

const int MAXN=200002;
int T,n,r[MAXN],c[MAXN],nowr,nowc,ans;
struct node
{
    int r,c;
    inline bool operator < (const node &x) const { return r<x.r; }
}e[MAXN];

int main()
{
    for(read(T);T;--T)
    {
        read(n);
        for (int i=1;i<=n;++i) read(e[i].r);
        for (int i=1;i<=n;++i) read(e[i].c);
        sort(e+1,e+n+1);
        nowr=1;
        nowc=1;
        ans=0;
        for (int i=1;i<=n;++i)
        {
            if(e[i].r==nowr&&e[i].c==nowc) continue;
            if(e[i].r==nowr+1)
            {
                if((nowr+nowc)&1)
                {
                    if(e[i].c!=nowc+1) ++ans;
                    nowr=e[i].r;
                    nowc=e[i].c;
                    continue;
                } else {
                    if(e[i].c!=nowc) ++ans;
                    nowr=e[i].r;
                    nowc=e[i].c;
                    continue;
                }
            }
            int d1=e[i].r-nowr;
            int d2=e[i].c-nowc;
            if((nowr+nowc)&1)
            {
                int calc=(d1-d2+1)/2;
                ans+=calc;
                nowr=e[i].r;
                nowc=e[i].c;
                continue;
            } else {
                if(d1-1<d2)
                {
                    ans+=d1;
                    nowr=e[i].r;
                    nowc=e[i].c;
                } else {
                    int calc=(d1-d2)/2;
                    ans+=calc;
                    nowr=e[i].r;
                    nowc=e[i].c;
                }
                continue;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}