本文共 2859 字，大约阅读时间需要 9 分钟。

代码实现与函数说明

#define ll long long
#define mem(a, b) memset(a, b, sizeof(a))
#define INF 0x3f3f3f3f
#define DNF 0x7f
#define DBG printf("this is a input\n")
#define fi first
#define se second
#define mk(a, b) make_pair(a, b)
#define pb push_back
#define p_queue priority_queue
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

数据预处理与结构定义

int T;
int n, x, y;
struct node {
    int x, y;
    bool operator<(const node& no) const {
        return x + y > no.x + no.y;
    }
};
// 数据存储
int a[1000005];
// 比较器
bool cmp(int x, int y) {
    return x > y;
}
int b[1000005], cnt1, cnt2;
int g[1000005], h[1000005], f[1000005];
int bg[1000005], sm[1000005];

数据预处理与结构定义

// 数据读取与分类
int main() {
    // 读取输入数据
    int T;
    scanf("%d", &T);
    while (T--) {
        mem(b, 0);
        mem(g, 0);
        mem(h, 0);
        mem(bg, 0);
        mem(sm, INF);
        
        scanf("%d", &n);
        
        a[0] = node{x, y}; // 结构体存储节点坐标
        
        for (int i = 1; i <= n; i++) {
            scanf("%d %d", &x, &y);
            if (x > y) {
                b[++cnt2] = x;
                b[++cnt2] = y;
            } else {
                a[++cnt1] = node{x, y};
            }
        }
        
        // 数据排序
        sort(b + 1, b + cnt2 + 1, cmp);
        sort(a + 1, a + cnt1 + 1);
        
        // 预处理g数组
        getgx();
        
        // 预处理h数组
        gethx();
        
        // 分治计算f数组
        getfx(1, 2*n, 0, 2*cnt1);
        
        // 输出结果
        cout << ...;
    }
}

代码实现与函数说明

// 预处理g数组
void getgx() {
    for (int i = 1; i <= cnt2; i++) {
        g[i] = g[i - 1] + b[i];
    }
}
// 预处理h数组
void gethx() {
    for (int i = 2; i <= 2*cnt1; i += 2) {
        h[i] = h[i - 2] + a[i / 2].x + a[i / 2].y;
    }
    
    // 背向推算bg数组
    for (int i = cnt1; i >= 1; i--) {
        bg[i] = max(bg[i + 1], a[i].x);
    }
    
    // 背向推算sm数组
    for (int i = 1; i <= cnt1; i++) {
        sm[i] = min(sm[i - 1], a[i].y);
    }
    
    // 前向推算h数组的结合值
    for (int i = 0; i <= cnt1; i++) {
        h[2*i + 1] = max(h[2*i] + bg[i+1], h[2*(i+1)] - sm[i+1]);
    }
}
// 分治计算f数组
void getfx(int l, int r, int L, int R) {
    if (l > r) {
        return;
    }
    if (L == R) {
        for (int i = l; i <= r; i++) {
            f[i] = g[i - L] + h[L];
        }
        return;
    }
    
    int mid = (l + r) >> 1;
    int pos, x = 0;
    
    // 确定决策点
    for (int i = max(L, mid - cnt2); i <= min(R, mid); i++) {
        if (x < g[mid - i] + h[i]) {
            x = g[mid - i] + h[i];
            pos = i;
        }
    }
    
    f[mid] = x;
    getfx(l, mid-1, L, pos);
    getfx(mid+1, r, pos, R);
}

主要功能简介