[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
输入示例
4 71 12 31 44 23 22 14 35 25 42 64 4
输出示例
12
数据规模及约定
见“试题描述”
题解
首先我们考虑一下只有一维（即只考虑草的价钱和牛对价钱的要求）的情况该怎么做，显然可以贪心，对于每个要求找到剩下的草当中最便宜的那个累计上就好了。现在无非多了一维新鲜度，所以我们按照新鲜度从大到小排遍序，剩下那一维就跟上面说的做法一模一样了。
#include#include #include #include #include #include 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 longstruct 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;}