贪心算法看这里~

· · 题解

题目大意

题目要求将两排砖按照以下条件排列：

  1. 前排的要严格矮于后排的。
  2. 每一排的价格从左到右需要是越来越贵（可以相等）。

贪心解法

这题算是很简单的贪心了。首先将两排砖分别按价格排序，价格相同的划到同一个 set。然后都从最低价开始，拿出前排当前最低价的一块砖摆上（多块的话随意摆一块），然后到后排的当前最低价的砖里面找一块刚好能满足要求的（刚好比前排的高 1 个单位，没有的话就是比这个高的最矮的），一直到摆完就可以了。要是这时候找不到这样的砖(就是最低价的都比前面的矮)，那就知道没法摆了（后排的有砖匹配不上前排，前排出现同样的情况也是一样），直接输出 impossible。

由于只需要遍历所有砖块一遍就可以解决，所以总时间复杂度是 O(n)。

代码时间（有点抽象）

#include <bits/stdc++.h>
using namespace std;
int n;
struct tile {
    int index;
    int price;
    int height;
};
int main() {
    cin >> n;
    vector<tile> front_row(n), back_row(n);
    //读数据，然后仅按价格排序
    auto read_tile = [&](vector<tile> &tile_row) {
        for (int i = 0; i < n; i++) {
            tile_row[i].index = i + 1;
            cin >> tile_row[i].price;
        }
        for (int i = 0; i < n; i++)
            cin >> tile_row[i].height;
        sort(tile_row.begin(), tile_row.end(), [&](const tile &a, const tile &b) { return a.price < b.price; });
    };
    read_tile(back_row);
    read_tile(front_row);
    //存储当前价格相同的tile
    //height -> iter in front/back row
    multimap<int,vector<tile>::iterator> front_tile_map, back_tile_map;
    int front_index = 0, back_index = 0;
    vector<int> front_ret(n),back_ret(n);
    int front_ret_index = 0, back_ret_index = 0;
    //插入当前价格的tile到set
    struct insert_map_arg{
        multimap<int,vector<tile>::iterator>& tile_map;
        vector<tile>& tile_vec;
        int& vec_index;
    }
        front_map_arg{front_tile_map, front_row, front_index},
        back_map_arg{back_tile_map, back_row, back_index};
    while (1) {
        auto insert_map=[&](insert_map_arg& arg){
            //每次都尝试insert front map和back map两者中空了的那个
            if (arg.tile_map.empty()) {
                int price = arg.tile_vec[arg.vec_index].price;
                while (arg.vec_index < arg.tile_vec.size() && arg.tile_vec[arg.vec_index].price == price) {
                    arg.tile_map.insert(make_pair(arg.tile_vec[arg.vec_index].height, arg.tile_vec.begin() + arg.vec_index));
                    ++arg.vec_index;
                }
            }
        };
        insert_map(front_map_arg);
        insert_map(back_map_arg);
        //用贪心法，从当前价格区间找出最合适的砖, 具体就是刚好和当前tile差一的
        if(front_tile_map.size() < back_tile_map.size()){
            for(auto t:front_tile_map){
                int frontH=t.second->height;
                auto iter=back_tile_map.lower_bound(frontH + 1);
                if(iter==back_tile_map.end()){
                    cout<<"impossible"<<endl;
                    return 0;
                }
                front_ret[front_ret_index++]=t.second->index;
                back_ret[back_ret_index++]=iter->second->index;
                back_tile_map.erase(iter);
            }
            front_tile_map.clear();
        } else{
            for(auto t:back_tile_map){
                int backH=t.second->height;
                auto iter=front_tile_map.upper_bound(backH-1);
                if(iter==front_tile_map.begin()){
                    cout<<"impossible"<<endl;
                    return 0;
                }
                iter=prev(iter);
                front_ret[front_ret_index++]=iter->second->index ;
                back_ret[back_ret_index++]=t.second->index;
                front_tile_map.erase(iter);
            }
            back_tile_map.clear();
        }
        if(front_ret_index>=n && back_ret_index>=n)
            break;
    }
    //输出答案
    for(auto i:back_ret)
        cout<<i<<" ";
    cout<<endl;
    for(auto i:front_ret)
        cout<<i<<" ";
    cout<<endl;
    return 0;
}

本代码需要使用 C++11 以上版本才可以，只因里面用了“auto”这个新东西~