[BZOJ1691][Usaco2007 Dec]挑剔的美食家
试题描述
与很多奶牛一样，Farmer John那群养尊处优的奶牛们对食物越来越挑剔，随便拿堆草就能打发她们午饭的日子自然是一去不返了。现在，Farmer John不得不去牧草专供商那里购买大量美味多汁的牧草，来满足他那N(1 <= N <= 100,000)头挑剔的奶牛。 所有奶牛都对FJ提出了她对牧草的要求：第i头奶牛要求她的食物每份的价钱不低于A_i(1 <= A_i <= 1,000,000,000)，并且鲜嫩程度不能低于B_i(1 <= B_i <= 1,000,000,000)。商店里供应M(1 <= M <= 100,000)种不同的牧草，第i 种牧草的定价为C_i(1 <= C_i <= 1,000,000,000)，鲜嫩程度为D_i (1 <= D_i <= 1,000,000,000)。 为了显示她们的与众不同，每头奶牛都要求她的食物是独一无二的，也就是说，没有哪两头奶牛会选择同一种食物。 Farmer John想知道，为了让所有奶牛满意，他最少得在购买食物上花多少钱。
输入
* 第1行: 2个用空格隔开的整数：N 和 M
* 第2..N+1行: 第i+1行包含2个用空格隔开的整数：A_i、B_i * 第N+2..N+M+1行: 第j+N+1行包含2个用空格隔开的整数：C_i、D_i
输出
* 第1行: 输出1个整数，表示使所有奶牛满意的最小花费。如果无论如何都无法 满足所有奶牛的需求，输出-1
输入示例
输出示例
数据规模及约定
见“试题描述”
题解
首先我们考虑一下只有一维（即只考虑草的价钱和牛对价钱的要求）的情况该怎么做，显然可以贪心，对于每个要求找到剩下的草当中最便宜的那个累计上就好了。现在无非多了一维新鲜度，所以我们按照新鲜度从大到小排遍序，剩下那一维就跟上面说的做法一模一样了。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std; int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
} #define maxn 100010
#define oo 2147483647
#define LL long long
struct Node {
int v, r;
Node() {}
Node(int _, int __): v(_), r(__) {}
} ns[maxn];
int ToT, rt, fa[maxn], ch[2][maxn];
void rotate(int u) {
int y = fa[u], z = fa[y], l = 0, r = 1;
if(z) ch[ch[1][z]==y][z] = u;
if(ch[1][y] == u) swap(l, r);
fa[u] = z; fa[y] = u; fa[ch[r][u]] = y;
ch[l][y] = ch[r][u]; ch[r][u] = y;
return ;
}
void insert(int& o, int v) {
if(!o) {
ns[o = ++ToT] = Node(v, rand());
return ;
}
bool d = v > ns[o].v;
insert(ch[d][o], v); fa[ch[d][o]] = o;
if(ns[ch[d][o]].r > ns[o].r) {
int t = ch[d][o];
rotate(t); o = t;
}
return ;
}
void del(int& o, int v) {
if(!o) return ;
if(v == ns[o].v) {
if(!ch[0][o] && !ch[1][o]) o = 0;
else if(!ch[0][o]) {
int t = ch[1][o]; fa[t] = fa[o]; o = t;
}
else if(!ch[1][o]) {
int t = ch[0][o]; fa[t] = fa[o]; o = t;
}
else {
bool d = ns[ch[1][o]].r > ns[ch[0][o]].r;
int t = ch[d][o]; rotate(t); o = t;
del(ch[d^1][o], v);
}
}
else {
bool d = v > ns[o].v;
del(ch[d][o], v);
}
return ;
}
int Find(int o, int v) {
if(!o) return oo;
if(ns[o].v == v) return v;
if(v < ns[o].v) return min(ns[o].v, Find(ch[0][o], v));
return Find(ch[1][o], v);
} struct Point {
int x, y; // x stands for money, y stands for freshness
Point() {}
Point(int _, int __): x(_), y(__) {}
bool operator < (const Point& t) const { return y > t.y; }
} cow[maxn], grs[maxn]; int main() {
int n = read(), m = read();
for(int i = 1; i <= n; i++) {
int x = read(), y = read();
cow[i] = Point(x, y);
}
for(int i = 1; i <= m; i++) {
int x = read(), y = read();
grs[i] = Point(x, y);
}
sort(cow + 1, cow + n + 1);
sort(grs + 1, grs + m + 1); LL ans = 0;
for(int i = 1, j = 1; i <= n; i++) {
while(j <= m && grs[j].y >= cow[i].y) insert(rt, grs[j].x), j++;
if(!rt) return puts("-1"), 0;
int tmp = Find(rt, cow[i].x);
if(tmp == oo) return puts("-1"), 0;
del(rt, tmp); ans += tmp;
}
printf("%lld\n", ans); return 0;
}