题解

这道题的核心是找到两排瓷砖的合法排列，满足三个条件：

1. 后排瓷砖高度 > 对应前排瓷砖高度
2. 每排瓷砖价格非递减
3. 两排瓷砖一一对应

解题思路

1. 分别排序：将后排和前排的瓷砖都按价格非递减排序，如果价格相同则按高度排序（后排按升序，前排按降序，这样更容易满足高度条件）
2. 双指针匹配：使用双指针法尝试为每个后排瓷砖找到合适的前排瓷砖
3. 验证合法性：确保匹配后的前排瓷砖价格不小于前一个，且高度小于对应后排瓷砖

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Tile {
    int price;
    int height;
    int index;
    
    Tile(int p, int h, int i) : price(p), height(h), index(i) {}
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    // 后排瓷砖：价格、高度、原始索引
    vector<Tile> back;
    for (int i = 0; i < n; i++) {
        int p;
        cin >> p;
        back.emplace_back(p, 0, i + 1);
    }
    for (int i = 0; i < n; i++) {
        cin >> back[i].height;
    }
    
    // 前排瓷砖：价格、高度、原始索引
    vector<Tile> front;
    for (int i = 0; i < n; i++) {
        int p;
        cin >> p;
        front.emplace_back(p, 0, i + 1);
    }
    for (int i = 0; i < n; i++) {
        cin >> front[i].height;
    }
    
    // 排序：后排按价格升序，价格相同按高度升序
    sort(back.begin(), back.end(), [](const Tile& a, const Tile& b) {
        if (a.price != b.price) return a.price < b.price;
        return a.height < b.height;
    });
    
    // 排序：前排按价格升序，价格相同按高度降序（更容易满足高度条件）
    sort(front.begin(), front.end(), [](const Tile& a, const Tile& b) {
        if (a.price != b.price) return a.price < b.price;
        return a.height > b.height;
    });
    
    // 双指针匹配
    vector<int> back_order(n);
    vector<int> front_order(n);
    int j = 0;
    bool possible = true;
    
    for (int i = 0; i < n; i++) {
        // 找到第一个价格 >= 前一个前排价格，且高度 < 当前后排高度的前排瓷砖
        while (j < n && (front[j].price < (i > 0 ? front_order[i-1] : 0) || front[j].height >= back[i].height)) {
            j++;
        }
        if (j >= n) {
            possible = false;
            break;
        }
        back_order[i] = back[i].index;
        front_order[i] = front[j].index;
        j++;
    }
    
    if (!possible) {
        cout << "impossible" << endl;
        return 0;
    }
    
    // 输出结果
    for (int i = 0; i < n; i++) {
        cout << back_order[i] << " ";
    }
    cout << endl;
    for (int i = 0; i < n; i++) {
        cout << front_order[i] << " ";
    }
    cout << endl;
    
    return 0;
}

代码解释

1. 数据结构：使用Tile结构体存储每个瓷砖的价格、高度和原始索引
2. 排序策略：
   • 后排瓷砖：按价格升序排列，价格相同时按高度升序，确保价格非递减
   • 前排瓷砖：按价格升序排列，价格相同时按高度降序，这样更容易找到满足高度条件的匹配
3. 双指针匹配：
   • 遍历后排瓷砖，为每个瓷砖找到合适的前排瓷砖
   • 要求前排瓷砖价格不小于前一个前排瓷砖价格（保证非递减）
   • 要求前排瓷砖高度小于当前后排瓷砖高度
4. 复杂度分析：排序时间复杂度为$O(n\log n)$，双指针遍历为$O(n)$，整体复杂度为$O(n\log n)$，适合$n \leq 5 \cdot 10^5$的规模

这种方法确保了所有条件都能被满足，并且高效地找到合法排列或判断不存在解。