题解：P13239 「2.48sOI R1」化妆品

· · 题解

下文中的人名，M 指 Misserina，S 指 ShenTianYi_。

题意简述

分析

一道有点恶心但是比较水的题目，建议难度黄。我们只需要将化妆品按时尚值和美丽值分别排序，得到两个索引数组 f[i] 和 b[i]（即这两个数组中存储的是排序后的值在原数组中的下标），再用四个指针分别指向两个排序数组的当前最小值和最大值位置。每次选择后，更新 M 和 S 各自的时尚值和美丽值，并更新指针跳过已选元素。

但是，一定要注意：一个化妆品被选中后，需同时更新两个索引数组的指针，才能避免重复选择（本蒟蒻正是因为这一点没考虑导致一开始 35pts）！为了方便地实现这一操作，我们可以定义一个 update() 函数。另外，指针移动时要检查边界，防止越界。

最后——

十年 OI 一场空，不开 long long 见祖宗。

记得开 long long！

下面是代码

码风良好，放心食用！
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 10; // 数组大小：2n (n ≤ 500,000)

int n;
int x[N], y[N];         // x[i]：第i个化妆品的时尚值，y[i]：美丽值
int f[N], b[N];         // f：按时尚值排序的索引数组，b：按美丽值排序的索引数组
bool vis[N];            // vis[i]：标记第i个化妆品是否已被选择
int curfl, curfr;       // 时尚值数组的指针：curfl（最小），curfr（最大）
int curbl, curbr;       // 美丽值数组的指针：curbl（最小），curbr（最大）
int m1, m2;             // M的总时尚值、总美丽值
int s1, s2;             // S的总时尚值、总美丽值

// 比较函数：按时尚值升序排序
bool cmpf(int a, int b) {
    return x[a] < x[b];
}

// 比较函数：按美丽值升序排序
bool cmpb(int a, int b) {
    return y[a] < y[b];
}

// 更新指针：确保四个指针指向未选元素
void update() {
    // 更新时尚值数组指针：跳过已选元素
    while (curfl <= curfr && vis[f[curfl]]) curfl++;
    while (curfl <= curfr && vis[f[curfr]]) curfr--;
    // 更新美丽值数组指针：跳过已选元素
    while (curbl <= curbr && vis[b[curbl]]) curbl++;
    while (curbl <= curbr && vis[b[curbr]]) curbr--;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // 读入数据
    cin >> n;
    curfl = 1, curfr = 2 * n; // 初始化指针：时尚值数组范围[1, 2n]
    curbl = 1, curbr = 2 * n; // 初始化指针：美丽值数组范围[1, 2n]

    // 读入时尚值并初始化索引
    for (int i = 1; i <= 2 * n; i++) {
        cin >> x[i];
        f[i] = i; // 索引初始为自身
    }
    // 读入美丽值并初始化索引
    for (int i = 1; i <= 2 * n; i++) {
        cin >> y[i];
        b[i] = i;
    }

    // 对索引数组排序：f按x升序，b按y升序
    sort(f + 1, f + 2 * n + 1, cmpf);
    sort(b + 1, b + 2 * n + 1, cmpb);

    // 处理n轮选择
    for (int i = 1; i <= n; i++) {
        int q;
        cin >> q; // 本轮指示：1-时尚最大，2-美丽最大

        update(); // 更新指针，确保指向未选元素

        if (q == 1) { // M选择时尚值最大
            // 1. M选时尚值最大的化妆品
            int idx = f[curfr];   // 当前时尚值最大的索引
            m1 += x[idx];         // 累加时尚值
            m2 += y[idx];         // 累加美丽值
            vis[idx] = true;      // 标记已选
            curfr--;              // 指针左移

            update(); // 更新指针（S选择前需跳过新选元素）

            // 2. S选时尚值最小的化妆品
            idx = f[curfl];       // 当前时尚值最小的索引
            s1 += x[idx];         // 累加时尚值
            s2 += y[idx];         // 累加美丽值
            vis[idx] = true;      // 标记已选
            curfl++;              // 指针右移
        } else { // M选择美丽值最大
            // 1. M选美丽值最大的化妆品
            int idx = b[curbr];   // 当前美丽值最大的索引
            m1 += x[idx];         // 累加时尚值
            m2 += y[idx];         // 累加美丽值
            vis[idx] = true;      // 标记已选
            curbr--;              // 指针左移

            update(); // 更新指针

            // 2. S选美丽值最小的化妆品
            idx = b[curbl];       // 当前美丽值最小的索引
            s1 += x[idx];         // 累加时尚值
            s2 += y[idx];         // 累加美丽值
            vis[idx] = true;      // 标记已选
            curbl++;              // 指针右移
        }
    }

    // 输出结果
    cout << m1 << ' ' << m2 << '\n'; // M的时尚值和美丽值
    cout << s1 << ' ' << s2 << '\n'; // S的时尚值和美丽值

    return 0;
}

时间复杂度为 O(n)（忽略 O(n \log n) 的排序）。