Gourmet Grazers 解题报告（poj3622 treap 平衡树 sort）

2018-03-18

~~大家好，我是...~~咳咳，废话不说直接上分析。

本文迁移自老博客，原始链接为 https://lookas2001.com/gourmet-grazers-%e8%a7%a3%e9%a2%98%e6%8a%a5%e5%91%8a/

题目解析

现有n头牛，m种草。对于每一头牛，吃的草价值不能小于ai并且吃的草绿色值不得小于bi；对于每一种草，都有草价值ci以及草的绿色值ci。要求，每一头牛有且仅有一种草与之对应且每一种草有且仅有一头牛与之对应。求满足条件的牛草搭配方式中，花费最少多少？

算法设计

初步想法，枚举暴力。

然后，我寻思着，求花费最少，首先我们需要先让我们的搭配满足条件。因为bi小的牛一定能吃bi大的牛所能吃的草，反之却不可以，另外，我们需要使得花费最少，如果优先处理bi小的牛很有可能会导致bi大的牛无法找到方案。所以我想着，可以对绿色值从大到小将牛与草排个序，先处理bi大的牛，然后再处理bi小的牛。

与此同时，就绿色值而言，可供牛选择的草会越来越多，在每一次处理牛之前，我们先把这些草加入到一个集合中。然后，我们在这个不断增加的集合中找到价格最少的草提供给牛吃，计入到最终的结果中。这个过程，维持这个有序集合我们使用平衡树来进行，下面的示例代码我使用了treap来实现。

错误分析

最开始总是WA，分析数据范围后发现，最终结果可能会非常大，所以我们需要用long long。
另外，如果使用treap，请一定要保证写的代码是准确的，否则会导致非常隐蔽的错误，比如在这里，我的treap的merge方法递归中传递的参数顺序错了，结果导致最终的集合无法保证顺序。
sort的结束位置是不会计入排序的。
一些很智障的访问越界可以使用Dev C++的debug来查，别忘了编译模式为debug而不是release，另外貌似win10下如果编译成64位会导致无法跟踪代码。（更新：其实并不是，切断点啥的都是可以的，但是如果程序中某个位置函数调用栈过大可能就显示不出来的）

示例代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

const int N = 110000;

int n, m;

struct cow_grass_d {
    int price, greenness;
} cow[N], grass[N];

struct node {
    int val, w;
    node *lc, *rc;
//  node *debug_self;
} mem[N];
node *mem_p;
node *root;

bool cmp(cow_grass_d a, cow_grass_d b) {
    return a.greenness > b.greenness;
}

void split(node *root, int key, node *&left, node *&right) {
    if (!root) {
        left = NULL;
        right = NULL;
        return;
    }
    if (root->val < key) {
        left = root;
        split(root->rc, key, left->rc, right);
    } else {
        right = root;
        split(root->lc, key, left, right->lc);
    }
}

void merge(node *left, node *right, node *&root) {
    if (!left) {
        root = right;
        return;
    }
    if (!right) {
        root = left;
        return;
    }
    if (left->w < right->w) {
        root = left;
        merge(left->rc, right, root->rc);
    } else {
        root = right;
        merge(left, right->lc, root->lc);
    }
}

//int lay = 0;
//void debug_print(node *p) {
//  if (!p) return;
//  lay++;
//  for (int i = 1; i < lay; i++) printf(" ");
//  printf("%p %p %p %d %d\n", p, p->lc, p->rc, p->val, p->w);
//  debug_print(p->lc);
//  debug_print(p->rc);
//  lay--;
//}

int main() {
//  freopen("input.txt", "r", stdin);

    scanf("%d%d", &n, &m);
    memset(cow, 0, sizeof cow);
    memset(grass, 0, sizeof grass);
    for (int i = 1; i <= n; i++) scanf("%d%d", &cow[i].price, &cow[i].greenness);
    for (int i = 1; i <= m; i++) scanf("%d%d", &grass[i].price, &grass[i].greenness);
    std::sort(cow + 1, cow + n + 1, cmp);
    std::sort(grass + 1, grass + m + 1, cmp);
//  for (int i = 1; i <= n; i++) printf("%d %d\n", cow[i].price, cow[i].greenness); printf("\n");
//  for (int i = 1; i <= m; i++) printf("%d %d\n", grass[i].price, grass[i].greenness); printf("\n");

    memset(mem, 0, sizeof mem);
    mem_p = mem;
    root = NULL;
    long long ans = 0;
    int j = 1;
    for (int i = 1; i <= n; i++) {
        for (; grass[j].greenness >= cow[i].greenness && j <= m; j++) {
            node *l, *r, *p;
            p = mem_p++;
            p->val = grass[j].price;
            p->w = rand();
            p->lc = p->rc = NULL;
//          p->debug_self = p;
            split(root, p->val, l, r);
            merge(l, p, l);
            merge(l, r, root);
//          printf("%d ", p->val);
        }
//      printf("\n");
//      debug_print(root);

        node *l, *r, *m, *p;
        split(root, cow[i].price, l, r);
        p = r;
        if (!p) {
            printf("-1");
            return 0;
        }
        while (p->lc) p = p->lc;
        ans += p->val;
//      printf("%d\n\n", p->val);
        merge(l, r, root);
        split(root, p->val, l, r);
        split(r, p->val + 1, m, r);
        merge(l, m->lc, l);
        merge(m->rc, r, r);
        merge(l, r, root); // 丢弃了m
    }
    printf("%lld", ans); // TIP 别忘了用long long哟

    return 0;
}